C-Klee in Solitary Confinement 思维

链接：https://codeforces.com/gym/103470/problem/C

题意：给一个数字序列，可以给一个子区间+k，要求输出众数最多的数量。

题解：
考虑一个区间+k带来的影响，这个区间内所有原本是a的数变成了a+k，所有是a-k的数变成了a。
于是如果想选择a为众数，选取的区间内所有a每个的贡献是-1，而区间内的a-k每个贡献是+1。
很容易想到，对于给定的a，只要找最大贡献的区间即可。

但是如果枚举a，肯定就超时了，这时需要思考优化
当我们枚举到第i个位置，这个位置的值是ai，可以发现它只对ai和ai+k产生贡献，也就是说，我们扫到第i个位置的时候统计ai和ai+k的答案，只需要扫一遍，就相当于枚举了全部的ai。
进一步我们可以发现，扫到ai时，它对ai产生了负贡献，而对ai+k产生了正贡献，所以我们仅需更新当众数是ai+k时的答案。

那么如何选取区间呢？从开始一直选取，只要到达某个位置的总贡献小于0就把这段区间扔掉，从新位置重新开始计算总贡献。

注：
这道题思想是边扫边找区间，边统计答案。
事实上，无需先确定区间，在枚举统计答案的过程中找到合适的区间即可。

#include<bits/stdc++.h>
using namespace std;
const int maxn=4e6+10;
int a[maxn];
int cnt[maxn];
int qjcnt[maxn];
int main(){
    ios::sync_with_stdio(0);
    int ans=0;
    int n,k;
    cin>>n>>k;
    for(int i=0;i<n;i++){
        cin>>a[i];
        a[i]+=2000000;
        cnt[a[i]]++;
        ans=max(ans,cnt[a[i]]);
    }
    for(int i=0;i<n;i++){
        qjcnt[a[i]]--;
        qjcnt[a[i]+k]++;
        if(qjcnt[a[i]]<0) qjcnt[a[i]]=0;
        ans=max(ans,qjcnt[a[i]+k]+cnt[a[i]+k]);
    }
    cout<<ans<<endl;
}

最后

以上就是舒适萝莉为你收集整理的C-Klee in Solitary Confinement 思维的全部内容，希望文章能够帮你解决C-Klee in Solitary Confinement 思维所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。