题解：P11837 [USACO25FEB] Making Mexes B

· · 题解

思路

这道题他是求在对于 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;
}