聚会

题目链接

链接：https://ac.nowcoder.com/acm/contest/5157/A
来源：牛客网

题目描述

牛牛过生日啦！他决定在家里举办一场生日聚会。
通往牛牛家里的道路正好是一条无限长的道路，为了简单起见，我们把它想象成一条直线——关于 xx 的数轴。其中牛牛的家位于(x=0)原点，想邀请(n)位朋友参加本次生日聚会，其中第(i)位朋友家居住在(x_i)的位置，初始他们同时以1单位每秒的速度从家里出发前往聚会的地点。
为了朋友们尽早到达聚会地点，拥有魔法的牛牛决定在道路上的整数点上建立两个传送门，这样朋友们可以通过传送门从一个位置瞬间传送到另一个位置。
现在请聪明的你帮牛牛算一算，在最优策略下，朋友们最晚需要多长时间可以到达聚会地点？(1≤x≤10^9,1≤n≤10^5)

思路：

容易想到有一个传送门在0点，再需考虑另一个传送门的位置即可。如果放在x>0的位置，那么x<0的点不送影响，反之也是。假设放在x>0的位置t，对于大于t的点，通过t传送到0最优，对于0到t之间的点，一定存在i到t传送到0最优，i-1直接到0最优。所以我们只需要去枚举这个i，让i-1前的点直接到0，i到n之间的点通过传送门t，把传送们t放在哪能够让i到n之间的点最近？当然是i到n的中间点！记得向上取整。

代码：

#include<bits/stdc++.h>
using namespace std;
vector<int> A,B;
int solve(vector<int> A,vector<int> B){
    int a=2e9,b=0;
    if(B.size())   b=B[B.size()-1];
    int n=A.size();
    for(int i=0;i<n;++i){
        if(i==0) a=min(a,(A[n-1]-A[0]+1)/2);
        else a=min(a,max(A[i-1],(A[n-1]-A[i]+1)/2 ));
    }
    return max(a,b);
}
int main(){
    int T,n;
    scanf("%d",&T);
    while(T--){
        A.clear();B.clear();
        scanf("%d",&n);
        for(int i=1;i<=n;++i){
            int x;
            scanf("%d",&x);
            if(x>0)
                A.push_back(x);
            else if(x<0)
                B.push_back(-x);
        }
        sort(A.begin(),A.end());
        sort(B.begin(),B.end());
        int ans=2e9;
        if(A.size())    ans=min(solve(A,B),ans);
        if(B.size())    ans=min(solve(B,A),ans);
        cout<<ans<<endl;
    }
    return 0;
}