Algoogle

Algorithm for Programming Contest

PKU 1989 The Cow Lineup

Category: PKU Tag: greedy

The Cow Lineup

問題概要


与えられる数列からできるの部分列を考える.
K以下の正整数を使った数列をその部分列から作るとき, 作れない数列が存在する最小の長さはいくらか.

解法


頭から1からKまで全て現れる連続した部分を1つと数えて,
そこからまた1からKまで全て現れる……としてその塊を数える. 明らかに全ての数列が作れる最大の長さはその数なので, その数+1が答え.

コード


(1989.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
25
26
27
28
29
30
#include <cstdio>
#include <cstring>

using namespace std;

int N, K;
int seq[100010];
bool used[10010];

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

Comments