Codeforces-1375-D-Replace by MEX

题意：

有一个长度为 n 的数组 a, \(0 \le a_i \le n\) .

一次操作可以选择数组中的任何元素，并将其替换为数组元素的MEX ( MEX是数组中未出现的最小自然数 ) .

请找到一个能让数组非递减的解决方案（保证操作数 2n 之内必有解决方案）。

思路：

保证操作数 2n 之内让数组最终变为 \([0,1,…,n?1]\) .（\(s[i] = i\)）

每一次操作：遍历数组，找到MEX。

? 如果 MEX < n ，就将它放到最终的位置上，即 s[MEX]。

? 如果 MEX = n，就遍历数组，找一个没有归位的位置，即 \(s[i] != i\) 的位置。

这样可以保证至多两个操作，就可以使一个数字归位。总操作数小于等于 2n。

AC代码：

#include<bits/stdc++.h>
using namespace std;
int s[1003];
int getMex(int n)
{
    vector<int> a(n + 1, 0);
    for (int i = 0; i < n; ++i) a[s[i]] = 1;
    for (int i = 0; i <= n; ++i) if (a[i] == 0) return i;
}
int check(int n)
{
    for (int i = 0; i < n; ++i) if (s[i] != i) return i;
    return -1;
}
inline void solve()
{
    vector<int> ans;
    int n; cin >> n;
    for (int i = 0; i < n; ++i) cin >> s[i];
    while (check(n) != -1)
    {
        int mex = getMex(n), pos = mex;
        if (mex == n) pos = check(n);
        s[pos] = mex;
        ans.push_back(pos);
    }
    cout << ans.size() << endl;
    for (auto i : ans)
        cout << i + 1 << " ";
    cout << endl;
}

int main()
{
    int T = 1; cin >> T;
    for (int i = 1; i <= T; ++i) solve();
    return 0;
}

Codeforces-1375-D-Replace by MEX

原文：https://www.cnblogs.com/Dont-Starve/p/13257874.html