題目大意

令 $mex$ 為序列中最小的沒有出現的數。

給你一個長度為 $n$ 的序列 $a$，你可以進行不超過 $2\times n$ 次操作，使得序列 $a$ 單調不降。每次操作你可以選定一個位置 $p$，并將 $a_p$ 賦值為 $mex$。請你輸出總共的操作次數與每次操作的位置。

解題思路

題目說了，$?x\in a,0\le x\le n$。所以，我們考慮將 $a$ 變為 $0,1,?,n?1$。

我們在進行操作時，需分成兩種情況討論。

• 若 $mex\ne n$，由于最后的序列要滿足 $a_i=i?1$，所以我們這里就將 $a_{mex+1}$ 賦值為 $mex$。
• 若 $mex=n$，那我們就找到序列中任意一個滿足 $a_i\ne i?1$ 的數，然后將其賦值為 $mex$。如果沒有找到，說明現在的序列已經滿足題意，不需要再進行操作了。

大概思路就是這樣。瞟了一眼數據范圍，發現 $n$ 比較小，于是我們在求 $mex$ 的值時可以暴力求解。

CODE：

#include <bits/stdc++.h>
using namespace std;
#define int long long
int 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;
}

總了個結

這題非常水，建議評綠。簡單構造，建議嘗試。