Algoogle

Algorithm for Programming Contest

PKU 2182 Lost Cows

Category: PKU Tag: implementation

Lost Cows

問題概要


解法


列の後ろからみていって, 番号の小さいやつから埋めていく
一番後ろのとき, 自分より小さい数の数は自分の数-1で, それと合致する場所を選べばよい
自分より小さい数を超えるたびにその比較の数を小さくしていく

コード


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

using namespace std;

int N;
int seq[8010];
int ans[8010];

int main(){
    scanf("%d", &N);
    for(int i = 1; i < N; i++)
        scanf("%d", seq+i);
    for(int i = 1; i <= N; i++){
        int cnt = i - 1;
        for(int j = N-1; j >= 0; j--)
            if(seq[j] == cnt) ans[j] = i;
            else if(ans[j] > 0) cnt--;
    }
    for(int i = 0; i < N; i++)
        printf("%d\n", ans[i]);
    return 0;
}

Comments