自动搬运

查看原文

来自洛谷，原作者为

	CashCollectFactory 这个家伙不懒，但什么都留下了

搬运于2025-08-24 22:52:20，当前版本为作者最后更新于2023-12-03 11:24:57，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

这一套 ICPC 的问题全是关于原神的诶，可莉好可爱，所以必须交一份题解来宠爱可莉呢~

思路简述

1. 统计各个数在不同位置上出现次数的前缀和。对于 $x$ 来说，它可由 $x$ 和 $x-k$ 得到，而一个区间内的众数可通过枚举不同的区间得到。

2. 用 $sum[i][0]$ 表示该数字 $x$ 在下标 $i$ 处出现了几次。

3. 用 $sum[i][1]$ 表示该数字 $x-k$ 在下标 $i$ 处出现了几次。

容易得到递推公式：$ans = sum[n][0]+sum[r][1]-sum[l-1][1]-(sum[r][0]-sum[l-1][0])$。

化简得到：$ans = sum[n][0]+sum[r][1]-sum[r][0]+sum[l-1][0]-sum[l-1][1]$。

依照此式进行前缀和（类似动态规划）即可，最终时间复杂度为 $O(n)$。

代码实现

#include <bits/stdc++.h>
using namespace std;
const int N=1e6+5;
int n,k,a[N],sum[N*4][2],mx,g,ans;
vector<int>e[N*4]; 
int main(){
    ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    cin>>n>>k;
    for(int i=1;i<=n;i++){
        cin>>a[i];a[i]+=2e6;
        e[a[i]].push_back(a[i]);
        e[a[i]+k].push_back(a[i]);
        g=max(g,a[i]+k);
        mx=max({mx,(int)e[a[i]].size(),(int)e[a[i]+k].size()});
    }
    if(!k){
        cout<<mx/2<<endl;
		 return 0;
    }
    for(int i=0;i<=g;i++){
        if(e[i].size()==0) continue;
        for(int j=0;j<e[i].size();j++){
            sum[j+1][0]=sum[j][0]+(e[i][j]==i);
            sum[j+1][1]=sum[j][1]+(e[i][j]!=i);
        }
        int tmp=sum[1][0]-sum[1][1];
        for(int j=1;j<=e[i].size();j++){
            tmp=max(tmp,sum[j-1][0]-sum[j-1][1]);
            ans=max(ans,sum[e[i].size()][0]+sum[j][1]-sum[j][0]+tmp);
        }
    }
    cout<<ans;
    return 0;
}