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';
}
}

评论
登录后参与技术讨论,分享你的经验与见解。
登录 / 注册暂无评论