自动搬运

查看原文

来自洛谷，原作者为

	da32s1da **

搬运于2025-08-24 22:07:03，当前版本为作者最后更新于2018-12-11 08:38:23，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

考虑将奶牛分组。

将$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
}