Algoogle

Algorithm for Programming Contest

PKU 3183 Stump Removal

Category: PKU Tag: implementation

PKU

問題概要


解法


左から順にみていって, 山になっているところで取り除く.
同じ数字が連続する場合次の山は下りから始めることにする.
最後にのぼりのまま終わった場合はNを出力する

コード


(3183.cpp) download
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <cstdio>

using namespace std;

int N;
int H[50010];

int main(){
    scanf("%d", &N);
    for(int i = 0; i < N; i++)
        scanf("%d", H+i);

    bool up = 1;
    int tail = 0;
    for(int i = 1; i < N; i++){
        if(up && H[i-1] < H[i]) continue;
        if(!up && H[i-1] > H[i]) continue;
        if(up) printf("%d\n", i);
        if(up && H[i-1] == H[i]) up = 0;
        up ^= 1;
    }
    if(up) printf("%d\n", N);
    return 0;
}

Comments