Replace by MEX

发布于 2020-07-07  0 次阅读


题目大意:

Replace by MEX

给定包含n个元素的数组a,每次通过MEX运算获得的值,可以用来替换a中的一个元素,通过不超过2n的操作,可以获得一个递增的数组b,输出操作次数,以及每次替换的a的元素的位置。

思路:

暴力将数组变成1~n

AC Code:

#include <stdio.h>
#include<iostream>
using namespace std;
#define maxn 1010
int cnt[maxn],a[maxn],ans[maxn<<1],k;
void change(int pos,int val){   //将pos位置变成val,并且更新标记
	cnt[a[pos]]--;
	cnt[val]++;
	a[pos]=val;
}
int main(){
	int t,n,i,tot,j;
	scanf("%d",&t);
	while(t--){
		scanf("%d",&n);
		for(i=1;i<=n;i++)
            cnt[i]=0;
		for(i=1;i<=n;i++)   
            scanf("%d",&a[i]),cnt[a[i]]++;
		tot=0,k=0;
		for(i=1;i<=n;i++)
			if(a[i]==i)
                tot++;
		if(tot==n){
            printf("0\n\n");
            continue;
        }
		while(1){
			for(i=0;i<=n;i++)
				if(!cnt[i])
                    break;
			if(i==0){
				for(j=1;j<=n;j++)
					if(a[j]!=j)
                        break;
				ans[++k]=j,change(j,0);
			}
            else{
				ans[++k]=i,change(i,i),tot++;
				if(tot==n)break;
			}
		}
		printf("%d\n",k);
		for(i=1;i<=k;i++)
            printf("%d ",ans[i]);
		printf("\n");
	}
	return 0;
}

平平无奇的大学在读本科生