题解：P6332 [COCI 2007/2008 #1] PRINOVA

zhuzifengzhuzifeng · 2026-11-10 16:13:28 · 题解

思路

题目就是要求一个点 x 到最近的 p_i 的距离的最大值，我们设 p_0 = 0,p_{n + 1} = + \infty ，那么点 x 一定在 p_i 和 p_{i + 1} 之间，所以我们可以枚举 i ，判断 p_i 到 p_{i + 1} 之间是否有 A 到 B 的值，有就先取最中间值，因为这样最优，再判断边界，但是最后还要判断如果 x = A 或 x = B 的时候，因为有时这样更优。

代码

#include<bits/stdc++.h>
#define PII pair<int,int>
#define int long long
using namespace std;
const int MAXN=1e6+5;
int n,a[MAXN],l,r,mx=-1e18,mxi;
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    //freopen(".in","r",stdin);
    //freopen(".out","w",stdout);
    cin>>n;
    for(int i=1;i<=n;i++)cin>>a[i];
    cin>>l>>r;sort(a+1,a+n+1);a[0]=0;a[n+1]=1e18;
    for(int i=0;i<=n;i++){
        if(!(r<a[i]||a[i+1]<l)){
            int x=(a[i+1]+a[i]+1)/2,z=x,L=max(a[i],l),R=min(a[i+1],r);
            x=x/2*2+1;
            if(x>R)x=R/2*2+1;if(x>R)x=R/2*2-1;
            if(x<L)x=L/2*2+1;
            int dist=min(abs(x-a[i]),abs(x-a[i+1]));
            if(dist>mx)mx=dist,mxi=x;
        }
    }int mi1=1e18,mi2=1e18;l=l/2*2+1;if(!(r&1))r--;
    for(int i=1;i<=n;i++)mi1=min(mi1,abs(l-a[i])),mi2=min(mi2,abs(r-a[i]));
    if(mi1>mx)mx=mi1,mxi=l;if(mi2>mx)mx=mi2,mxi=r;
    cout<<mxi;
    return 0;
}