D. Replace by MEX(MEX的性质)

Problem - 1375D - Codeforces

 题意:

你得到了一个由0到n之间的整数组成的数组。

在一次操作中，你可以选择数组中的任何一个元素，并用数组中元素的MEX来替换它（操作后可能会改变）。

例如，如果当前数组是[0,2,2,1,4]，你可以选择第二个元素，并用当前元素的MEX-3替换它，数组将变成[0,3,2,1,4]。

你必须使数组不递减，最多使用2n次操作。

可以证明，这总是可能的。请注意，你不一定要使运算次数达到最小。如果有很多解决方案，你可以打印其中任何一个。

 -

当且仅当b1≤b2≤...≤bn时，一个数组b[1...n]是不递减的。

一个数组的MEX（最小排除）是不属于该数组的最小的非负整数。比如说。

[2,2,1]的MEX是0，因为0不属于这个数组。
3,1,0,1]的MEX是2，因为0和1都属于数组，但是2不属于数组。
0,3,1,2]的MEX是4，因为0，1，2和3都属于这个数组，但是4不属于。
值得一提的是，一个长度为n的数组的MEX总是在0和n之间（含）。

输入
第一行包含一个整数t（1≤t≤200）--测试案例的数量。下面是测试用例的描述。

每个测试用例的第一行包含一个整数n（3≤n≤1000）--数组的长度。

每个测试用例的第二行包含n个整数a1,...,an (0≤ai≤n) - 数组的元素。注意，它们不一定是独立的。

保证所有测试用例的n之和不超过1000。

输出
对于每个测试案例，你必须输出两行。

第一行必须包含一个整数k（0≤k≤2n）--你执行的操作数。

第二行必须包含k个整数x1,...,xk(1≤xi≤n)，其中xi是为第i个操作选择的索引。

如果有许多解决方案，你可以找到其中任何一个。请记住，并不要求最小化k。

题解:

由于数据范围很小,只有1000,并且不要求最小化k,所以我们可以考虑暴力的做法

直接让他每一位a[i] = i即可

每次找mex

如果mex = n,就让最后一位为n,然后n--,就不用考虑后面的操作了

否则,直接让a[mex] = mex 

#include<iostream>
#include<algorithm>
#include<map>
#include<cstring>
#include<vector> 
using namespace std;
int a[1004];
int vis[1004];
int n;
int find()
{
	memset(vis,0,sizeof vis);
	for(int i = 0;i < n;i++)
	vis[a[i]] = 1;
	for(int i = 0;i < n;i++)
	{
		if(!vis[i])
		return i;
	}
	return n;
}
void solve()
{
	cin >> n;
	int f = 0;
	for(int i = 0;i < n;i++)
	{
		cin >> a[i];
		if(i > 0&&a[i-1]>a[i])
		{
			f = 1;
		}
	}
	if(!f)
	{
		cout<<"0\n\n";
		return ;
	}
	vector<int> ans;
	while(n)
	{
		int mex = find();
		if(mex == n)
		{
			a[n-1] = n;
			ans.push_back(n-1);
			n--;
		}
		else{
			a[mex] = mex;
			ans.push_back(mex);
		}
		
	}
	cout<<ans.size()<<"\n";
	for(auto k:ans)
	{
		cout<<k+1<<" ";
	} 
	cout<<"\n";
}
int main()
{
	int t;
	cin >> t;
	while(t--)
	{
		solve();
	}
	
}