[CF1375D] Replace by MEX - 构造

Description

给定一个长度为 \(n\) 的数列，可以进行不超过 \(2n\) 次操作，每次可以选择一个位置，将它的值设为当前整个数列的 mex。构造一种操作方案，使得整个数列的值单调不降。

Solution

我们考虑将整个数列做成 \(0,1,2,...,n-1\) 的形式。我们给出一种构造方案使得能在不超过 \(2n\) 步内将任何一个序列做成这种形式。

当整个数列的 mex 小于 n 时，执行 A 类操作，即将 \(a[mex+1]\) 赋值为 \(mex\)；否则，执行 B 类操作，任意找一个不满足 \(a[i]=i-1\) 的位置，将 \(a[i]\) 赋值为 \(mex=n\)。

显然每一个 B 类操作后一定紧跟着一个 A 类操作，而一个 A 类操作会搞定一个位置，并且这个位置以后再也不会被操作到。

#include <bits/stdc++.h>
using namespace std;

#define int long long

int Mex(vector<int> vec)
{
	vector<int> tmp(vec.size() + 2, 0);
	for (auto i : vec)
		if (1ull * i < 1ull * vec.size())
			tmp[i]++;
	int ans = 0;
	while (tmp[ans])
		++ans;
	return ans;
}

void solve()
{
	int n;
	cin >> n;

	vector<int> a(n + 2, 0);
	for (int i = 1; i <= n; i++)
		cin >> a[i];

	vector<int> ans;

	while (true)
	{
		vector<int> tmp;
		for (int i = 1; i <= n; i++)
			tmp.push_back(a[i]);
		int mex = Mex(tmp);
		if (mex == n)
		{
			int pos = 0;
			for (int i = 1; i <= n; i++)
				if (a[i] != i - 1)
				{
					pos = i;
					break;
				}
			if (pos)
			{
				a[pos] = n;
				ans.push_back(pos);
			}
			else
			{
				break;
			}
		}
		else
		{
			a[mex + 1] = mex;
			ans.push_back(mex + 1);
		}
	}

	cout << ans.size() << endl;
	for (int i : ans)
		cout << i << " ";
	cout << endl;
}

signed main()
{
	ios::sync_with_stdio(false);

	int t;
	cin >> t;
	while (t--)
	{
		solve();
	}

	return 0;
}

[CF1375D] Replace by MEX - 构造

原文：https://www.cnblogs.com/mollnn/p/14157098.html