题目传送门

题意简述

数轴上有 $R$ 个点，现在在数轴上选择一个任意的点 $P$（可以与这 $R$ 个点重合），在原来的 $R$ 个点中选出尽可能多的点且使得这些点到 $P$ 的距离之和小于等于 $B$。问最多能选出几个点。

题解

用我们在小学二年级就学过的知识可知，对于数轴上的任意一些点（排好序）：

• 如果这些点的数量为奇数，那么到这些点距离之和最小的点就是中间点；
• 如果是偶数，那么到这些点距离之和最小的点可以在中间两个点之间的任意一个位置。

利用以上性质，我们可以在确认这些选出的点的情况下得到点 $P$ 的位置。

首先可以想到，将点排序后，选出的点一定是连续的，这里令最左边的点为第 $l$ 个点，最右边的点为第 $r$ 个点。

这张图中一共有 $9$ 个点，中间点为 $E(P)$，$P$ 将数轴分为两部分。

设 $P$ 的坐标为 $x$，左侧某点的坐标为 $x_i$，右侧某点的坐标为 $x_j$，则左侧点的贡献为 $x-x_i$，右侧点的贡献为 $x_j-x$。

由于两侧点的个数是相等的，所以 $x$ 消掉了，只剩下右侧坐标和减去左侧坐标和，可以用前缀和预处理。

对于偶数，将 $P$ 放在中间两点中间，同样是右侧坐标和减去左侧坐标和。

令 $sum$ 为前缀和数组，则有公式 $(mid=\dfrac{l+r}{2})$：

• 奇数：$sum_{r}-sum_{mid}-(sum_{mid}-sum_{l-1})$
• 偶数：$sum_{r}-sum_{mid}-(sum_{mid-1}-sum_{l-1})$

（这样写虽不美观但更符合思路）。

至于 $l$ 和 $r$，注意到 $l$ 增加时 $r$ 肯定不会减小，因此可以双指针。

总时间复杂度 $O(n)$。

杂事

love_luogu 想 c 我的 tj，请管理员严查！！！（虽然 ta 已经过了）

AC Code

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+5;
const int M=2e5+5;
const int inf=2147483647;
const long long lof=9223372036854775807;
#define ll long long
#define bug cout<<"...here..."<<endl;
#define mem(a,b) memset(a,b,sizeof a)
#define CLOSE ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define int ll
int n,l,b,ans;
int a[N],sum[N];
signed main(){
    CLOSE
    cin>>n>>l>>b;
    for(int i=1;i<=n;i++) cin>>a[i],sum[i]=sum[i-1]+a[i];
    int r=1;
    for(int l=1;l<=n;l++){
        while(({//从讨论区学来的神秘写法，解释往下看
            int res=0,mid=l+(r+1)>>1;//要判断r+1是否可以
            if((l+r+1)&1) res=sum[r+1]-sum[mid]-(sum[mid]-sum[l-1]);
            else res=sum[r+1]-sum[mid]-(sum[mid-1]-sum[l-1]);//前面是计算
            (r<n&&res<=b);//这里是while语句继续循环的条件
        })) r++;
        ans=max(ans,r-l+1);//取最大值
    }
    cout<<ans;
    return 0;
}