C. MEX Repetition

原创于 2023-09-30 11:21:52 发布 · 粉丝可见 · 1.4k 阅读 · 0 · 0 · 本内容遵循CC 4.0 BY-SA版权协议版权声明：本文为博主原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。 GEO检测 · 编辑
文章链接：https://blog.csdn.net/hacker_51/article/details/133429315

题目：

样例：

`cobol<br/>5<br/>1 2<br/>1<br/>3 1<br/>0 1 3<br/>2 2<br/>0 2<br/>5 5<br/>1 2 3 4 5<br/>10 100<br/>5 3 0 4 2 1 6 9 10 8<br/>`

1 2 0 1 2 1 2 3 4 5 0 7 5 3 0 4 2 1 6 9 10

思路：

从题目和样例中，我们可以知道，从一个数组中，按照包括0的自然数的顺序查找确实的一个顺序，然后按从左到右进行交换。想法和思路弄清楚后，暴力模拟肯定是不行的了，数据范围过大，k的数据范围是 1e9, n 的数据范围是 1e5,在加上 t 的数据范围 1e5，如果纯暴力,按照最坏的情况，时间复杂度大概是 10 的19次方。所以基本不可能的。

我们可以看一下样例，可以发现一个规律，那就是第一次缺少的包括0的自然数 x ，在输出样例中，会去掉前面或者后面，然后将该 x 放置前面或者后面。我们可以猜测，并可以知道，某次交换后，可能会和前面少的一次效果很可能相同，即根据长度 n ，k % n + 1次操作和 k 次操作效果相同，这里 k % n + 1 是当 k % n 刚好整除的时候，k 次操作应该有效的，即至少有一次有效操作，所以 k % n + 1，可以缩短了 k 的数据范围，并且缩短了时间复杂度，其次该 x 不是在前就是在后，并且中间基本顺序不会变，我们又可以猜测，并且有点接近了前后队列的操作性质，估计是双端队列的操作。

即 k % n + 1 次的将后端放置前端，然后按照原数组个数，顺序输出队列。

代码详解如下：

#include <iostream>
#include <vector>
#include <queue>
#include <cstring>
#include <algorithm>
#include <unordered_map>
#define endl '\n'
#define YES puts("YES")
#define NO puts("NO")
#define umap unordered_map
#define All(x) x.begin(),x.end()
#pragma GCC optimize(3,"Ofast","inline")
#define ___G std::ios::sync_with_stdio(false),cin.tie(0), cout.tie(0)
using namespace std;
const int N = 2e6 + 10;

inline void solve()
{
	int n,k,x = 0;
	cin >> n >> k;
	
	// 存储双端队列
	deque<int>q;
	
	// 标记数组中的包括0自然数是否出现过
	umap<int,bool>r;
	
	for(int i = 0,num;i < n;++i)
	{
		cin >> num;
		
		// 按照顺序存储好原数组
		q.push_back(num);
		
		// 标记好出现过的包括0自然数
		r[num] = true;
		
		// 寻找按照顺序没出现过的包括0自然数
		while(r[x]) ++x;
	}
	
	// 存储好 x 在尾端，然后根据 k 进行放前端
	q.push_back(x);
	
	// k 次操作 与 k %= n + 1 次操作效果相同
	// 有效缩短时间复杂度
	k %= n + 1;
	
	// k 次操作 队列，将尾端放置前端
	while(k--)
	{
		q.push_front(q.back());
		q.pop_back();
	}
	
	// 按照原个数，顺序输出操作完后的数组
	while(n--)
	{
		cout << q.front() << ' ';
		q.pop_front();
	}
	cout << endl;
}
int main()
{
//	freopen("a.txt", "r", stdin);
	___G;
	int _t = 1;
	cin >> _t;
	while (_t--)
	{
		solve();
	}
	return 0;
}