专栏文章
题解:CF2025C New Game
CF2025C题解参与者 1已保存评论 0
文章操作
快速查看文章及其快照的属性,并进行相关操作。
- 当前评论
- 0 条
- 当前快照
- 1 份
- 快照标识符
- @minznqrm
- 此快照首次捕获于
- 2025/12/02 10:58 3 个月前
- 此快照最后确认于
- 2025/12/02 10:58 3 个月前
单调队列
我们先用 map 统计出每个数出现的次数,接着将 数组排序并去重,维护一个大小不超过 的相邻元素差值为 的单调队列即可。
CPPconst 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 条评论,欢迎与作者交流。
正在加载评论...