Meximum Array

Meximum Array,第1张

Meximum Array

Codeforces Round #767 (Div. 2),C题Meximum Array
可以用双指针在O(n)的复杂度内求解。
先用num数组存一下每个数字出现的次数,然后跑一遍num,贪心找到当前最大MEX。之后用双指针枚举a数组,删除数组中0-MEX-1的数字(一共有MEX个,可以重复删,但是每个数字都要删到),期间可以开个vis数组,并用cnt统计一下删除的数字个数。注意到如果有数字删完了一定要及时更新MEX。
最后注意一下数组清空问题,一定不要在双指针内直接vector< int >vis(n+1),这样写,会被卡成O(n^2),然后TLE!请用for清空数组。

具体代码如下:

#include 
using namespace std;
const int N=2e5+5;
int n,a[N],num[N];
bool vis[N];
void solve()
{
	int mex=0;
	vectorans;
	cin>>n;
	for(int i=1;i<=n;i++) cin>>a[i];
	for(int i=1;i<=n;i++) num[a[i]]++;
	while(num[mex]>0) mex++;
	for(int i=1;i<=n;i++)
	{
		int now=mex,cnt=0;
		ans.push_back(now);
		for(int j=i;j<=n;j++)
		{
			num[a[j]]--;
			if(num[a[j]]==0&&a[j]T;
	while(T--) solve();
	return 0;
}

欢迎分享,转载请注明来源:内存溢出

原文地址: http://outofmemory.cn/zaji/5710975.html

(0)
打赏 微信扫一扫 微信扫一扫 支付宝扫一扫 支付宝扫一扫
上一篇 2022-12-18
下一篇 2022-12-17

发表评论

登录后才能评论

评论列表(0条)

保存