题解：P11837 [USACO25FEB] Making Mexes B

· · 题解

题目

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

思路

显然地，要让每一个 i 满足条件的条件有两个：

  1. 从 0 到 i-1 中的每一个数都出现过，即需要补全在序列中 i 前面的空缺。

  2. 使 i 在序列中没有出现过，即将序列中全部的 i 移走。

那么我们就会发现可以将 i 移到前面的空缺上来补齐，这样的操作次数一定是最小的。因此答案就是这两个做法中的最大值。

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

不过对于 0 来说需要特判，因为它没有在前面的数，所以答案就是 0 的数量。

代码

#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;
}