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

· · 题解

题目

题意

给定长度为 n 的偶数序列 p_{1},p_{2},…,p_{n} 和两个整数 A,B。寻找一个奇数 X，满足 A\le X\le B，使得 \min_{1\le i\le n} \left | X- p_{i} \right | 尽可能大。

输出任意一个满足条件的 X。

思路

我们观察到，要使 \min_{1\le i\le n} \left | X- p_{i} \right | 尽量大，X 应该尽可能远离所有偶数。因此 X 一定出现在：

我们只要把这些候选奇数都找出来，逐一计算它们到所有偶数的距离的最小值，记录下最优解即可。

代码如下

#include<bits/stdc++.h>
using namespace std;
const int MAXN=105;
int n,p[MAXN],A,B;
vector<int> cand;//用来收集候选奇数
int main(){
    ios::sync_with_stdio(0);cin.tie(0);
    cin>>n;
    for(int i=0;i<n;i++){
        cin>>p[i];
    } 
    cin>>A>>B;
    sort(p,p+n);//对偶数序列进行排序
    //边界候选：A附近
    if(A%2==1) cand.push_back(A);
    else if(A+1<=B) cand.push_back(A+1);
    //边界候选：B附近
    if(B%2==1) cand.push_back(B);
    else if(B-1>=A) cand.push_back(B-1);
    //每对相邻偶数之间的候选
    for(int i=0;i+1<n;i++){
        int sum=p[i]+p[i+1];//两个偶数之和
        int mid=sum/2;//中间值（可能为奇数或偶数）
        //尝试mid-1，mid，mid+1中的奇数
        for(int d=-1;d<=1;d++){
            int x=mid+d;
            if(x%2==1&&A<=x&&x<=B){
                cand.push_back(x);
            }
        }
    }
    //枚举候选，计算最优解
    int bestX=(A%2==1?A:A+1);//“保底”答案（区间内第一个奇数）
    int bestdist=-1;
    for(int x : cand){
        int mindist=2e9; 
        for(int i=0;i<n;i++){
            int dist=abs(x-p[i]);
            if(dist<mindist) mindist=dist;
        }
        if(mindist>bestdist){
            bestdist=mindist;
            bestX=x;
        }
    }
    cout<<bestX;
    return 0;
}