P11837 [USACO25FEB] Making Mexes B

题目描述

给定一个包含 $N$ 个非负整数的数组 $a$，$a_1,a_2,\dots ,a_N$（$1\le N\le 2\cdot 10^5$，$0\le a_i\le N$）。在一次操作中，你可以将 $a$ 的任一元素修改为任意非负整数。

一个数组的 mex 是它不包含的最小非负整数。对于范围 $0$ 到 $N$ 内的每一个 $i$，计算使 $a$ 的 mex 等于 $i$ 所需要的最小操作次数。

输入格式

输入的第一行包含 $N$。

以下一行包含 $a_1,a_2,\dots ,a_N$。

输出格式

对于范围 $0$ 到 $N$ 内的每一个 $i$ 输出一行，包含对于 $i$ 的最小操作次数。注意，$a$ 的 mex 对于范围 $0$ 到 $N$ 内的任意 $i$ 值都是可以通过修改取到的。

输入输出样例 #1

输入 #1

4
2 2 2 0

输出 #1

1
0
3
1
2

说明/提示

样例 1 解释：

• 为使 $a$ 的 mex 等于 $0$，我们可以将 $a_4$ 修改为 $3$（或任何正整数）。在得到的数组 $[2,2,2,3]$ 中，$0$ 是数组不包含的最小非负整数，因此 $0$ 是数组的 mex。

• 为使 $a$ 的 mex 等于 $1$，我们不需要进行任何修改，因为 $1$ 已经是 $a=[2,2,2,0]$ 中不包含的最小非负整数。

• 为使 $a$ 的 mex 等于 $2$，我们需要修改 $a$ 的前三个元素。例如，我们可以将 $a$ 修改为 $[3,1,1,0]$。

• 测试点 $2\sim 6$：$N\le 10^3$。

• 测试点 $7\sim 11$：没有额外限制。

C++实现

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+10;
int n,a[N],cnt;
int main(){
cin>>n;
for(int i=1;i<=n;i++){
int b;
cin>>b;
a[b]++;
}
cout<<a[0]<<endl;
for(int i=1;i<=n;i++){
cnt=cnt+(!a[i-1]);
if(cnt>a[i]) cout<<cnt<<endl;
else if(a[i]>cnt) cout<<a[i]<<endl;
else if(a[i]==cnt) cout<<cnt<<endl;
}
return 0;
}

后续

接下来我会不断用C++来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现，记录日常的编程生活、比赛心得，感兴趣的请关注，我后续将继续分享相关内容