自动搬运

查看原文

来自洛谷，原作者为

	Jameswood 吾辈踯躅不前，无畏前路坎坷，无问同行无人，但忧道中花未央

搬运于2025-08-24 22:14:54，当前版本为作者最后更新于2020-10-31 00:46:11，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

题目大意

在一个数轴上，有给定数量和位置的点（可以重合，位置恒正且为整数）。你的任务是选取其中的一个点作为比较点。之后在给出的点中选择一部分，使得选择的点的总数尽可能大，且它们到你所选择的比较点的距离之和（费用）小于等于题目给出的上限 $B$。你需要输出可选择点的总数的最大值（收获的农田数目的最大值）。

阅前必读

事先声明：

1. 本篇题解偏新手向，大佬们只需阅读概要部分即可。

2. 作者是一只菜菜的木头酱，如有异议/错误欢迎提出/指出 QAQ 。

本篇题解提供以下三种做法：

1. 暴力模拟【都会做吧……先不讲了，有需要下方留言，看到会更新的】
2. 前缀和+二分答案【时间复杂度 $O(nlogn)$】 【正解】
3. 前缀和+双向指针【时间复杂度 $O(n)$】 【理论最优解】

前置数学知识：绝对值不等式 、 绝对值的几何意义

综合难度评定：普及＋/提高 中较难的一类，如果真的要思考的很透彻的话个人认为可以够到一点点省选难度（绝对值不等式【中位数】 + 前缀和 + 二分答案 + 原题面英文理解困难）

详细解答

本题的关键在于如何快速地在选择两个给定点后计算出这一区间内所有给定点到区间内任一比较点距离之和的最小时的花费。这里将运用绝对值不等式进行说明。（链接内提供说明和证明）

对于已经确定的某一区间，设其中包含的给定点为 $a_1,a_2,$ ... $, a_{m-1},a_m$ （ 其中 $a_1\leq a_2 \leq ... \leq a_{m-1} \leq a_m$ ）

那么对于选中的比较点 $a_k$ （$1\leq k \leq m$） 。其距离之和（总花费）可以表示为 $\vert a_k-a_1\vert+\vert a_k-a_2 \vert + ... + \vert a_{m-1}-a_k \vert + \vert a_m - a_k\vert$ （参考：绝对值的几何意义）

当 $m$ 为偶数时，我们对其从首尾开始两两分组，即：

$(\vert a_k-a_1\vert+\vert a_m-a_k \vert) + ... + ( \vert a_k-a_{\frac{m}{2}} \vert + \vert a_{\frac{m}{2}+1} - a_k\vert)$ ①

接下来对每一组使用绝对值不等式，可以得到：

① $ \geq( a_m-a_1 ) + ( a_{m-1}-a_2 ) ... + ( a_{\frac{m}{2}+1} - a_{\frac{m}{2}} )$

等号当且仅当在 $(a_k-a_{\frac{m}{2}}) \times (a_{\frac{m}{2}+1} - a_k)\geq0$ ，即$a_{\frac{m}{2}}\leq a_k \leq a_{\frac{m}{2}+1}$时成立

（注：当发现无法把某一组中的 $a_k$ 消掉时说明你没有理解绝对值不等式的真正含义，解决方法可以简单地把其中一个在绝对值符号内乘以负一）

当 $m$ 为奇数时，我们可以把第 m/2+1 项单独提出，之后就能进行类似的操作，得到 总费用 $ \geq( a_m-a_1 ) + ( a_{m-1}-a_2 ) ... + ( a_{m/2+2} - a_{m/2} )$ ，注意需要将取等条件修改为 $a_k=a_{m/2+1}$ 即可。

$\color{red}\colorbox{#f8f8f9}{综上所述}$，我们可以得到：在选定的以两个给定点 $a_1$ 、$a_m$ 为端点的闭区间内，当比较点 $a_k = a_{m/2+1}$ 时，给定点的数目将会取到最大值，其值如上述。只需要对给定点的坐标之和使用前缀和维护，即可做到 $O(n)$ 查询（注：我认为如果到此步各位没有理解困难的话应该可以推出利用前缀和快速求区间费用的通式QAQ，没什么想法的先把 ① 再读一边，然后还不行就点链接，有详细说明）。

接下来我们开始寻找符合要求的区间，如果只求通过的话，可以运用二分思想。依次从 $x_1$ 开始一直遍历到 $x_R$ 查找区间的左端点，之后二分查找每一个左端点 $x_i$ 对应的右端点 $x_j$ 使得收获的农田最多。

代码如下：

#include<cstdio>
#include<cstdlib>
using namespace std;
const int SIZE=1e5+5;
long long R,L,B,ans,mid;
long long x[SIZE],sum[SIZE];
inline long long max(long long a,long long b){
	if(a>b) return a;
	else return b;
}
long long check(long long l,long long r){
	mid=l+r>>1;
	return x[mid]*(mid*2-l-r)+sum[l-1]+sum[r]-sum[mid]-sum[mid-1];
}
int main(){
	scanf("%lld%lld%lld",&R,&L,&B);
	for(long long i=1;i<=R;i++){
		scanf("%lld",&x[i]);
		sum[i]=sum[i-1]+x[i];
	}
	long long l,r,mid,k;
	for(long long i=1;i<=R;i++){
		l=i;r=R;
		while(l<=r){
			mid=l+r>>1;
			if(check(i,mid)<=B){
				l=mid+1;k=mid;
			}
			else r=mid-1;
		}
		ans=max(ans,k-i+1);
	}
	printf("%lld",ans);
	return 0;
}

附通过记录

而对于双向指针，其思想也相当简单。初始时选定区间 $[x[1],x[1]]$（此时花费为0，肯定满足要求）。 接下来把第二个 $x[1]$ 的下标右移，每右移一次判断一次。当总花费超过 $B$ 时则将第一个 $x[1]$ 的下标右移一，然后再判断总花费是否满足要求，是则右移右端点，否则右移左端点，以此类推，得到结果。（其正确性基于输入的 $x_i$ 单调递增，故右端点不需要在左端点右移后左移）

#include<cstdio>
#include<cstdlib>
using namespace std;
const int SIZE=1e5+5;
long long R,L,B,ans,mid;
long long x[SIZE],sum[SIZE];
inline long long max(long long a,long long b){
	if(a>b) return a;
	else return b;
}
long long check(long long l,long long r){
	mid=l+r>>1;
	return x[mid]*(mid*2-l-r)+sum[l-1]+sum[r]-sum[mid]-sum[mid-1];
}
int main(){
	scanf("%lld%lld%lld",&R,&L,&B);
	for(long long i=1;i<=R;i++){
		scanf("%lld",&x[i]);
		sum[i]=sum[i-1]+x[i];
	}
	for(long long l=1,r=1;l<=R;l++){
		while(r<R&&check(l,r+1)<=B) ++r;
		//此处r忽略了 [x[1],x[1]] 的区间，并以 r+1 和 r<R作为判断依据
		//是为了便于计算ans
		ans=max(ans,r-l+1);
	}
	printf("%lld",ans);
	return 0;
}

附通过记录

代码中与详解不同的部分已用注释阐明。本题的重难点其实是在 check 函数里，请各位小心，不要错估其难度所在。

最后：如有疑问欢迎提出，木头酱看到后会回复在评论区。

以上，希望这篇题解能够帮到泥们QWQ