题解 P5093 【[USACO2004OPEN]The Cow Lineup 奶牛序列】

· · 题解

考虑将奶牛分组。

将1...k中的每个数字都出现的连续一段分成一组。

例如，样例分成[1,5,3,2,5,1,3,4],[4,2,5,1,2,3]两组。

容易发现，每一组的最后一个数字一定是在这一组中最后出现且只出现一次。

所以！把每个组的最后一个数字取出来，然后剩下的组不成一组的，必然存在没有出现的数字，将其取出。

所以答案是组数+1。

#include<cstdio>
#include<cstring>
const int N=10050;
int n,k,x;
int vis[N],tot,ans;
int main(){
    scanf("%d%d",&n,&k);
    for(int i=1;i<=n;i++){
        scanf("%d",&x);
        if(!vis[x])vis[x]=1,tot++;
        if(tot==k){
            //形成完整的一组，清空vis，累加答案。
            memset(vis,0,sizeof(vis));
            tot=0;
            ans++;
        }
    }
    printf("%d\n",ans+1);//组数+1
}