The Cow Lineup

思路

• 将整个数组进行分割，使每个子数组都包含1~k至少一次
• 我们可以选取每个子数组最后一个数，再加上任意一个数即可组成最短不存在子序列

代码

// Problem: The Cow Lineup
// Contest: NowCoder
// URL: https://ac.nowcoder.com/acm/problem/106586
// Memory Limit: 60000 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <iostream>
#include <cstring>
using namespace std;
#define mst(abc,bca) memset(abc,bca,sizeof abc)
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
const int N=10010;
bool st[N];
int main(){
    ios::sync_with_stdio(0);cin.tie(0);
    int n,k,num=0,ans=1;
    cin>>n>>k;
    rep(i,1,n){
        int x;cin>>x;
        if(!st[x]) st[x]=1,num++;
        if(num==k){
            ans++,num=0;
            mst(st,0);
        }
    }
    cout<<ans<<"\n";
    return 0;
}