~~這是蒟蒻的第一篇題解，巨犇輕點噴~~

思路

显然地，要让每一个

i

满足条件的条件有两个：

从 $0$ 到 $i-1$ 中的每一个数都出现过，即需要补全在序列中 $i$ 前面的空缺。
使 $i$ 在序列中没有出现过，即将序列中全部的 $i$ 移走。

那么我们就会发现可以将

i

移到前面的空缺上来补齐，这样的操作次数一定是最小的。因此答案就是这两个做法中的最大值。

计算各个数字出现的次数用桶来做就可以了。

不过对于

0

来说需要特判，因为它没有在前面的数，所以答案就是

0

的数量。

代码

CPP

#include<bits/stdc++.h>
#define N 200005
using namespace std;
int a[N],n,tot;
int main()
{
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		int x;
		scanf("%d",&x);
		a[x]++;
	}
	printf("%d\n",a[0]);  //0的特判
	for(int i=1;i<=n;i++)
	{
		if(!a[i-1]) tot++;  //统计i前面共有多少个数没有出现过
		printf("%d\n",max(tot,a[i]));  //计算两者中的最大值
	}
	return 0;
}

题解：P11837 [USACO25FEB] Making Mexes B

文章操作

思路

代码

相关推荐

评论

题解：P11837 [USACO25FEB] Making Mexes B