自动搬运

查看原文

来自洛谷，原作者为

	chenqishuo **

搬运于2025-08-24 23:10:39，当前版本为作者最后更新于2025-03-03 21:31:13，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

思路

这道题他是求在对于 $i$ 最少需要修改多少次才能使 $0$ 到 $i$ 中不包含的最小非负整数为 $i$。

对于 $i$ 我们要求不包含的最小非负整数，自然就要知道 $i$ 之前不包含的最小非负整数的个数。如果对于 $i$ 我们再去循环 $0$ 到 $i - 1$ 统计数量的话，那么复杂度就会变成 $O(n^2)$，看一看数据范围 $1 \le N \le 2 \times 10^5$ 不用说肯定炸烂掉。

那怎么办呢？我们可以定义一个 $cnt$ 变量在枚举 $i$ 时来统计 $i$ 之前不包含的最小非负整数的个数。在统计之前需要将输入的数进行一个整合，就是计算每个数的数量，当这个数的数量为 $0$ 时，$cnt$ 增加 $1$，也就是 cnt++;。

接下来就是判断至少需要修改多少次。经过观察我们可以发现：

1. 当 $cnt$ 为 $0$ 时，说明 $i$ 之前没有不包含的最小非负整数。这时如果 $i$ 的数量为 $0$，那么 $i$ 为不包含的最小非负整数，修改次数就为 $0$ 次。

2. 当 $cnt$ 为 $0$ 时，如果 $i$ 的数量不为 $0$，意味这 $i$ 为包含的非负整数，要令不包含的最小非负整数为 $i$，就需要把所有的 $i$ 修改为不为 $i$ 的值，修改次数就为 $i$ 的个数。

3. 当 $cnt$ 不为 $0$ 时，说明 $i$ 之前有不包含的最小非负整数。就需要把这 $cnt$ 个数各用一个数代替，如果 $i$ 这个数的个数小于等于 $cnt$ 时，我们就可以用所有的 $i$ 和其他有多余的数进行修改，直到刚好将这 $cnt$ 个数都代替，修改次数就为 $cnt$。

4. 当 $cnt$ 不为 $0$ 时，且 $i$ 这个数的个数大于 $cnt$ 时，我们就可以用所有的 $i$ 进行修改，直到刚好将这 $cnt$ 个数都代替，剩余的部分全部修改不为 $i$ 数，修改次数为 $i$ 的个数。

剩下的就可以交给代码实现了。

代码

时间复杂度：$O(n)$

#include <iostream>

using namespace std;

const int N = 2e5 + 10;
int a[N];

int main()
{
	int n;
	cin >> n;
	for(int i = 1;i <= n; ++ i)
	{
		int x;
		cin >> x;
		a[x] ++; //计算每个相同的数的数量
	}
	
	long long cnt = 0;
	
	for(int i = 0;i <= n; ++ i)
	{
		if(cnt > a[i])
			cout << cnt << endl;
		else cout << a[i] << endl;
//------------------------------------------------
//计算i之前不包含的最小非负整数的个数
		if(a[i] == 0)
			cnt ++;
	}
	return 0;
}