C、MEX Repetition

跳转原题点击此：该题地址

1、题目大意

  给定一个数组，要求每次依次从左到右将\(a_i\)替换为当前数组的最小非负整数（每次替换一个数后，最小非负整数也会发生改变）。问你，经过k次的操作后，最终数组是什么。
  注意：该数组的数 和 最小非负整数，是从\(0,1,\cdots,n\)这一共\(n + 1\)个数中选出，每个数必须出现一次。

2、题目解析

  我们发现，每次更换数组时，\(a_1\)会被最小非负整数替换，而\(a_2\)则会被\(a_1\)原来的书替换，以此类推，而\(a_n\)原本的数则会称为新的最小非负整数。
  所以，令最小非负整数为\(x\)，则其与原数组生成新的数组：\(a_1,a_2,\cdots,a_n,x\)。
  第一次MEX新数组变为\(x,a_1,a_2,\cdots,a_{n-1},a_n\)，\(a_n\)变为新的最小非负整数。所以每次MEX都会将新数组往后移动一格，最后一个到第一个来。
  同时我们注意到，每\(n+1\)次MEX后，数组将会重新变为输入时的数组，所以我们可以对其取余，减少重复操作。

#include<bits/stdc++.h>

using namespace std;

int T;
int n, k;

// 定义第一个最小的非负整数为x，原输入为a1,a2,...,an
// 原理在于：每次都是x覆盖第一个数，然后后面的数依次用前一个被替代的数覆盖
// 所以发现：a1,a2,...,an,x，第一次为x,a1,a2,...a(n-1),an，每次MEX都将数组往后移动一格
void solve()
{
	cin >> n >> k;
	vector<int>f(n + 1);
	set<int>se;
	for(int i = 0; i < n; i++)
	{
		cin >> f[i];
		se.insert(f[i]);
	}
	for(int i = 0; i <= n; i++)
	{
		if(!se.count(i))
		{
			f[n] = i;
			break;
		}
	}
	k %= (n + 1);	// 因为当k次数为n+1的倍数则与输入无异
	if(k == 0)	
		k = n + 1;
	int cnt = n, idx = n - k + 1;	// idx为k次MEX后的第一个头下标
	while(cnt--)
	{
		// 注意顺序：先输出头下标，如何下标++，如果超过范围则返回第一个
		cout << f[idx] << " ";
		idx++ ;
		if(idx == n + 1)
			idx = 0;
	}
	cout << endl;
	
}

int main()
{
	cin >> T;
	while (T--)
	{
		solve();
	}

	return 0;
}