【每日一题】3月3日The Cow Lineup

题意

题目意思很简单 就是给定一个序列a 然后让你找一个序列b 他不是这个序列a的的子序列 求这个序列b的最短的长度

那么怎么做呢

举个例子吧

10 4

1 2 3 4 1 2 3 4 1 2

我们看首先都出现过 所以最小的很明显不能取其中的一个

然后我们再看

把这四个数分为三组

1 2 3 4 | 1 2 3 4 | 1 2

这里我们就可以看出来了

第一组包含了的所有数字 第二组也包含了

那么我们如果取长度为2的序列 明显这个序列是包含了所有的

所以我们最少要取到三 这样前面两个数字都有但是第三个数字就可以取 3 或者4了

因此得到的序列就是一定不是那个序列的子序列了

所以我们的做法就是将原序列按是否包含了分组 然后答案就是包含了所有的组数+1就是答案了

code

#include <stdio.h>
#include <string.h>
typedef long long ll; typedef unsigned long long ull; typedef long double ld;
const ll MOD = 1e9 + 7;

const int N = 1e5 + 7;
const int INF = 0x3f3f3f3f;
bool vis[N];

int main(void){
    int n , m;
    scanf("%d%d" , &n , &m);
    ll ans = 0;
    ll cnt = 0 ;
    for(int i = 1 ; i <= n ; ++i){
        int k ;
        scanf("%d" , &k);
        if(!vis[k]){
            cnt++;
            vis[k] = 1;
            if(cnt == m){
                cnt = 0 ;
                ans++;
                memset(vis , 0 , sizeof(vis));
            }
        }
    }
    printf("%d\n" , ans + 1);
    return 0;
}