题解：CF2025C New Game

Meickol · 2025-09-06 21:06:37 · 题解

单调队列

我们先用 map 统计出每个数出现的次数，接着将 a 数组排序并去重，维护一个大小不超过 k 的相邻元素差值为 1 的单调队列即可。

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;
}