思路
- 将整个数组进行分割,使每个子数组都包含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;
}