D. Replace by MEX 思维

题意

  给你一个长度为n的序列,值在0到n之间,你每次都可以指定任意一个位置,使这个位置的值变成当前的mex,要求使整个序列变得非递减的,问输出每次操作的下标。答案可任意。

思路

  我们考虑如何讲序列变成1 2 ... n这样一个特定的序列,这样就满足了题意的非递减。

  我们将a[i]!=i的下标称之为失序的,每次求得一个mex,如果它是0,我们就把它放到一个失序的位置,如果mex不是0,我们就把他放到mex的位置,也就让a[mex]=mex,也就处理好一个失序的位置了,每一个失序的位置最多通过2次就可以处理好,故通过2n次一定可以调整好整个序列。时间复杂度为n方。

AC代码

include<iostream>

include<vector>

include<string.h>

using namespace std;
const int maxn=1e3+5;
int t,n;
int a[maxn],vis[maxn];
vector<int> ans;
int mex()
{

int vis2\[maxn\];
memset(vis2,0,sizeof(vis2));
for(int i=1;i<=n;i++){
    vis2\[a\[i\]\]++;
}
for(int i=0;i<=n;i++){
    if(vis2\[i\]==0) return i;
}

}
int main()
{

cin>>t;
while(t--){
    cin>>n;
    memset(vis,0,sizeof(vis));
    ans.clear();
    int num=0;
    for(int i=1;i<=n;i++){
        cin>>a\[i\];
        if(a\[i\]!=i) {
            vis\[i\]=1;
            num++;
        }
    }
    while(num){
        int now=mex();
        //cout<<"\*"<<now<<endl;
        if(now==0){
            for(int i=1;i<=n;i++){
                if(vis\[i\]==1){
                    //cout<<"0&&"<<a\[i\]<<endl;
                    a\[i\]=0;
                    ans.push\_back(i);
                    break;
                }
            }
            continue;
        }
        
        a\[now\]=now;
        vis\[now\]=0;
        ans.push\_back(now);;
        num--;
    }
    cout<<ans.size()<<'\\n';
    for(auto x:ans){
        cout<<x<<" ";
    }
    cout<<'\\n';
}

}

评论

暂无评论