CF1375D Replace by MEX 题解

题目传送门

题目大意

令 $mex$ 为序列中最小的没有出现的数。

给你一个长度为 $n$ 的序列 $a$，你可以进行不超过 $2\times n$ 次操作，使得序列 $a$ 单调不降。每次操作你可以选定一个位置 $p$，并将 a p a_p ap​ 赋值为 $mex$。请你输出总共的操作次数与每次操作的位置。

解题思路

题目说了，$\forall x\in a,0\le x\le n$。所以，我们考虑将 $a$ 变为 $0,1,\cdots ,n-1$。

我们在进行操作时，需分成两种情况讨论。

• 若 $mex\ne n$，由于最后的序列要满足 a i = i − 1 a_i=i-1 ai​=i−1，所以我们这里就将 a m e x + 1 a_{mex+1} amex+1​ 赋值为 $mex$。
• 若 $mex=n$，那我们就找到序列中任意一个满足 a i ≠ i − 1 a_i \\neq i - 1 ai​=i−1 的数，然后将其赋值为 $mex$。如果没有找到，说明现在的序列已经满足题意，不需要再进行操作了。

大概思路就是这样。瞟了一眼数据范围，发现 $n$ 比较小，于是我们在求 $mex$ 的值时可以暴力求解。

时间复杂度约为 O( n 2 T) \\mathcal{O}(n^2T) O(n2T)。

简单证明

但是肯定有很多同学以为以上算法的操作次数可能大于 $2n$，在独立做这道题时把这个思路给扔了。

我们不妨简单理解一下。

由于我们每一次操作都把 a m e x + 1 a_{mex + 1} amex+1​ 赋值为 $mex$ 或者将任意一个满足 a i ≠i−1 a_i \\neq i - 1 ai​=i−1 然后把 a i a_i ai​ 赋值为 $mex$，那么最多操作 $n$ 次就能使序列中出现了 $0\sim n-1$ 这 $n$ 个数，只是不一定单调不降，所以我们需要再操作至多 $n$ 次，使得单调不降，总操作次数最大为 $2n$。

$2025$ 年 $5$ 月 $12$ 日新增：
由于觉得上文可能说得不太清楚，所以下文更加详细地说明了这个结论，因此上文看不懂没有关系，直接看下文就行。

也就是说如果操作 $1$ 总共至多执行 $n$ 次，因为执行 $n$ 次后任意位置都满足 a m e x =mex−1 a_{mex} = mex - 1 amex​=mex−1。操作 $2$ 也至多执行 $n$ 次，因为将满足 a i ≠i−1 a_i \\neq i - 1 ai​=i−1 的 a i a_i ai​ 赋值为 $n$（因为这时 $mex=n$）只是为了将 a i a_i ai​ 上原本存储的值放回原位，再将 a a i + 1 a_{a_{i} + 1} aai​+1​ 赋值为 me x 2 mex_2 mex2​，以此类推，相当于一个连锁反应，因此操作 $1$ 加上操作 $2$ 的总操作次数不会超过 $2n$。

CODE：

#include using namespace std;#define int long longint a[1010], b[2010], vis[1010];signed main() {ios::sync_with_stdio(false); cin.tie(0), cout.tie(0);int t, n;cin >> t;while (t--) {memset(vis, 0, sizeof vis);cin >> n;for (int i = 1; i <= n; i++) {cin >> a[i];vis[a[i]]++; }int ans = 0; //总共的操作次数/*最后a[i] = i - 1 */while (1) {int mex = 0;for (int i = 0; i <= n; i++) { //查找 mexif (!vis[i]) {mex = i;break;}}if (mex != n) {vis[a[mex + 1]]--;b[++ans] = mex + 1;a[mex + 1] = mex;vis[mex]++;} else { bool f = 0;for (int i = 1; i <= n; i++) {if (a[i] != i - 1) { f = 1;vis[a[i]]--;a[i] = mex;vis[mex]++;b[++ans] = i;break;}} if (!f) //序列合法，不需要再进行操作了  break;}}cout << ans << endl;for (int i = 1; i <= ans; i++)cout << b[i] << \' \';cout << endl;}return 0;}