题解 P6332 【[COCI2007-2008#1] PRINOVA】

· · 题解

一个策略：如果使得 \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 的限制，讨论就没有必要了。