专栏文章

题解:CF2025C New Game

CF2025C题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性,并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@minznqrm
此快照首次捕获于
2025/12/02 10:58
3 个月前
此快照最后确认于
2025/12/02 10:58
3 个月前
查看原文

单调队列

我们先用 map 统计出每个数出现的次数,接着将 aa 数组排序并去重,维护一个大小不超过 kk 的相邻元素差值为 11 的单调队列即可。
CPP
const int N=2e5+5;
int n,k;
int a[N];
int q[N];
void solve(){
	cin>>n>>k;
	map<int,int> mp;
	rep(i,1,n){
		cin>>a[i];
		mp[a[i]]++;
	}
	sort(a+1,a+1+n);
	int m=unique(a+1,a+1+n)-(a+1);
	int hh=1,tt=0;
	int res=0,ans=0;
	rep(i,1,m){
		while(hh<=tt && a[i]!=a[q[tt]]+1) res-=mp[a[q[tt]]],tt--;
		q[++tt]=i;
		if(q[hh]<i-(k-1)) res-=mp[a[q[hh]]],hh++;
		res+=mp[a[q[tt]]];
		ans=max(ans,res);
	}
	cout<<ans;
}

评论

0 条评论,欢迎与作者交流。

正在加载评论...