【Mex *** 作】【思维】【CF】A. Meximum Array

【Mex *** 作】【思维】【CF】A. Meximum Array

博客主页: https://blog.csdn.net/qq_50285142欢迎点赞⭐️收藏⭐️❤️关注❤️留言  如有错误，敬请指正 一看一温习，一码一收获

链接：
https://codeforces.com/problemset/problem/1628/A

每次可以对数组a前k个元素取mex *** 作，将所得数值加到b数组中，取完后删去a中的前k个元素，求数组b最大字典序为多少。

---

肯定是尽可能前面mex往大的取，尽可能的大。
要想最大，就是需要找a数组前缀mex使其是数组a的最大mex。

找完之后就对vis数组进行更新（全变为false），意味着已经找到原来数组的最大mex，删去那个最大mex的前缀，在a数组中接下来的区间再次执行相同的 *** 作（寻找最大mex）

---

代码解释：
cnt[i]:数字i出现的次数
tmp:维护数组a前缀的mex值

每当cnt[tmp]==0时，就是说这个mex值，在数组a后面没有出现过了，这个就是最大的mex值，把它加到res结果中。
注意cnt[]数组是动态变化的，每次访问一个值a[i],就执行了cnt[a[i]]--的 *** 作，cnt[]始终代表的是数组a当前元素后面的值出现的次数统计

---

数组a的前缀取Mex *** 作：

vis[i]:代表数组中数字i是否出现,需要从前往后进行维护，不能一下预处理完
tmp:代表从第一个元素开始到当前的元素，mex值为tmp

int tmp = 0;
for(int i=1;i<=n;i++)
{
	vis[a[i]] = true;//维护vis
	while(vis[tmp]) tmp++;
}

---

AC代码：

#include
using namespace std;
const int N = 2e5+5;

int a[N];
int n;

void solve()
{
	int n;
	cin>>n;
	vectorcnt(n+1,0);
	vectorvis(n+1,false);
	for(int i=1;i<=n;i++)
	{
	 	cin>>a[i];
		cnt[a[i]]++;
	 } 
	
	vectorres;
	int tmp = 0;
	for(int i=1;i<=n;i++)
	{
		vis[a[i]] = true;
		while(vis[tmp]) tmp++;
		cnt[a[i]] --;
		if(!cnt[tmp])
		{
			res.push_back(tmp);
			vis = vector(n+1,false);
			tmp = 0;
		}
	}
	cout<>t;
	while(t--) solve();
	return 0;
 } 

往期优质文章推荐

C++ STL详解，超全总结(快速入门STL) 李【期末复习】c++知识点大回顾，八篇文章让你永不破防（一）区间贡献问题习题详解