Codeforces 1375D Replace by MEX（思维题）

题意：给出一个长度为n的数组，0<=a【i】<=n，每一次操作可以把任意一个a【i】换成mex，求多少次操作使得数组a为非递减序列，输出操作次数和操作的i，任意一种满足情况的即可。n<1e3

题解：尝试直接构造0，1，2---n-1这样的序列，分两种情况，mex！=n的时候把mex交换到a【mex】=mex；当mex=n时，找一个不满足a【i】=i的位置替换即可，不然会死循环。

#include <bits/stdc++.h>
#define IO_read ios::sync_with_stdio(false);cin.tie(0)
#define fre freopen("C:\in.txt", "r", stdin)
#define _for(i,a,b) for(int i=a; i< b; i++)
#define _rep(i,a,b) for(int i=a; i<=b; i++)
#define inf 0x3f3f3f3f
#define lowbit(a) ((a)&-(a))
using namespace std;
typedef long long ll;
template <class T>
void read(T &x)
{
    char c; bool op=0;
    while(c=getchar(), c<'0'||c>'9') if(c=='-') op=1;
    x=c-'0';
    while(c=getchar(), c>='0'&&c<='9') x=x*10+c-'0';
    if(op) x=-x;
}

const int maxn=1e3+5;
int T, n, a[maxn];
int k, vis[maxn];
vector<int> vec;

int mex()
{
    _for(i, 0, n) if(!vis[i]) return i;
    return n;
}

int find_pos()
{
    _for(i, 0, n) if(a[i]!=i) return i;
    return -1;
}

int main()
{
    //fre;
    read(T);
    while(T--)
    {
        read(n);
        memset(vis, 0, sizeof(vis));
        k=0, vec.clear();
        _for(i, 0, n) read(a[i]), vis[a[i]]++;
        while(true)
        //for(int i=1; i<=2*n; i++)
        {
            int p=find_pos();
            if(p==-1) break;
            int x=mex();
            if(x==n){
                vis[a[p]]--, a[p]=x, vis[a[p]]++;
                k++, vec.push_back(p);
            }
            else{
                vis[a[x]]--, a[x]=x, vis[a[x]]++;
                k++, vec.push_back(x);
            }
        }
        printf("%d
", k);
        for(auto &v: vec) printf("%d ", v+1);
        printf("

");
    }
    return 0;
}