自动搬运

查看原文

来自洛谷，原作者为

	y0y68 AFO

搬运于2025-08-24 22:19:45，当前版本为作者最后更新于2020-04-09 20:43:44，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

一个策略：如果使得 $\min{\{|X-p_i|}\}$ 最大（以下都假设 $p_1$ 到 $p_n$ 是按升序排列的，而且不考虑奇偶性，代码中再考虑），那么 $X$ 必在 $p_i$ 和 $p_{i+1}$ 的最中间（$1 \le i < n$）或是对于 $X$ 的边界，因为在某块 $p_i$ 到 $p_{i+1}$ 的区间之内，离边界（这里指 $p_i$ 或 $p_{i+1}$）的距离是比和其他 $p_i$ 的距离近的，而要想离这个边界最远，就得在这个边界的最中间，也可能是 $X$ 的边界是因为下边界是 [下边界，$p_1$] 这个区间中离 $p_1$ 最远的点（前提是下边界小于等于 $p_1$ ），上边界同理。详细见代码中的注释：

#include<bits/stdc++.h>
using namespace std;
int n,l,r,p[105];
//这里的l,r分别表示题目中的A和B
int main(){
	cin>>n;
	for(int i=1;i<=n;i++)
		cin>>p[i];
	cin>>l>>r;
	sort(p+1,p+n+1);
	int mx=-1,ans,tmp,dis;
	//mx为目前所有的  tmp分别和所有p[i](1≤i≤n)的差的最小值  的最大值
	//ans为目前最佳的点
	//tmp为循环中在p[i]和p[i+1]之间最佳的点
	//dis为循环中的min(tmp-p[i],p[i+1]-tmp)的值
	//（也就是tmp分别和所有p[i](1≤i≤n)的差的最小值）
	for(int i=1;i<n;i++){
		if(p[i]>=l&&p[i+1]<=r){
			//情况1：p[i]和p[i+1]在区间限制范围内
			tmp=p[i]+p[i+1]>>1;
			//这句话相当于tmp=(p[i]+p[i+1])/2;
			if(tmp%2==0)tmp++;
			//若是偶数，则要变成奇数（题目中说的,这里也可以写成tmp--;）
			dis=min(tmp-p[i],p[i+1]-tmp);
			//计算和p[i]还是p[i+1]的距离近
		}
		else if(p[i]>=l&&p[i]<=r&&p[i+1]>r){
			//情况2：p[i]在范围内，p[i+1]出了边界
			tmp=p[i]+p[i+1]>>1;
			if(tmp%2==0)tmp--;
			//为保证答案是奇数
			//而且因为这里p[i+1]>r所以一定要tmp--
			if(tmp>r)tmp=r;
			//如果出了边界就设置为上界
			if(tmp%2==0)tmp--;
			//如果上界为偶数就-1成奇数
			dis=min(tmp-p[i],p[i+1]-tmp);
			//次操作同情况1，下面这种操作就不写注释了
		}
		else if(p[i]<l&&p[i+1]>=l&&p[i+1]<=r){
			//这种情况和情况2很类似，如果看不懂请类比情况2理解
			tmp=p[i]+p[i+1]>>1;
			if(tmp%2==0)tmp++;
			if(tmp<l)tmp=l;
			if(tmp%2==0)tmp++;
			dis=min(tmp-p[i],p[i+1]-tmp);
		}
		else if(p[i]<l&&p[i+1]>r){
			//情况4：p[i]出下界，p[i+1]出上界
			tmp=p[i]+p[i+1]>>1;
			if(tmp<l)tmp=l;
			else if(tmp>r)tmp=r;
			//上面这两句话请类比情况2和3的类似语句理解
			if(tmp%2==0)
			//如果为偶数
				if(tmp==r)tmp--;
				//等于r则减一，否则加一
				else tmp++;
			dis=min(tmp-p[i],p[i+1]-tmp);
		}
		if(dis>mx)mx=dis,ans=tmp;
		//如果现在的dis是目前最大的，则更新最大值和答案
	}
	if(r%2==0)r--;
	//考虑边界，如果r是偶数，那么r--，注意不能r++
	if(r>=p[n]&&r-p[n]>mx)ans=r,mx=r-p[n];
	//这里如果情况最好一定要注意更新最大值，否则只有90分
	if(l%2==0)l++;
	//同理
	if(l<=p[1]&&p[1]-l>mx)ans=l;
	cout<<ans<<endl;
	return 0;
}

可能你会问为什么不考虑 $p_{i+1}<A$ 和 $p_i>B$ 的情况，因为在这两种情况中，区间 $p_i$ 到 $p_{i+1}$ 内的任意一个数都不满足大于大于 $A$ 小于等于 $B$ 的限制，讨论就没有必要了。