牛客挑战赛39 A.聚会

solution：
设mx为最大点的坐标，mi为最小点的坐标的绝对值。
不妨设mi<mx。
则上限为mx。
首先有一个结论：一定有一个点在原点。证明如下：
分类讨论，不妨设左边叫A，右边叫B。
若A<B<0：这种答案就为上限。
若A<0<B：
在这种情况下，A、B绝对值较小的那一边的所有点的距离一定为|x|。因为跨传送门显然不优。
根据假设，我们发现一定是|A|<|B|的。（否则答案仍为上限）
也就是说只有右边的点会用到传送门，如果要用传送门的话，付出的代价为|A|+点到B的距离。
|A|显然为0是最优的。
若0<A<B：这种情况和上种证明类似，可知|A|一定不会>0。

那么问题变成了：数轴上有点集S，你需要选择一个点作为关键点P，dis定义为min(x to 0 , x to P)，使得maxdis最小。

按照坐标排序后，显然，一定是前面一部分直接去0，后面的所有点去P。
枚举i，表示i前面的点去0，i+1-n去P。则此时贡献为max(x[i],(x[n]-x[i+1]+1)/2)。取个最小值即可。
注意别忘了还要和mi取max。

复杂度O(nlogn)，瓶颈在排序。

代码如下：

#include<bits/stdc++.h>
using namespace std;
inline int read()
{
    int s=0,w=1;
    char ch=getchar();
    while(ch<'0'||ch>'9') {if(ch=='-') w=-1;ch=getchar();}
    while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
    return s*w;
}
#define mid ((l+r)>>1)
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define REP(x) for(int i=head[x],y=a[i].to;i;i=a[i].next,y=a[i].to) if(y!=fa)
#define FOR(i,a,b) for(int i=a;i<=b;i++)
typedef long long ll;
typedef long double ld;
const int N=1010100;
int x[N],n,mx,mi,ans,sta[N],top;
const int INF=1e9+10;
int main()
{
    int T=read();
    while(T--) {
        n=read();
        mx=mi=ans=top=0;
        for(int i=1;i<=n;i++) {
            x[i]=read();
            if(x[i]>=0)mx=max(mx,abs(x[i]));
            else mi=max(mi,abs(x[i]));
        }
        if(mi>mx) {
            for(int i=1;i<=n;i++) x[i]=-x[i];
            swap(mx,mi);
        }
        for(int i=1;i<=n;i++) {
            if(x[i]<=0) ans=max(ans,abs(x[i]));
            else sta[++top]=x[i];
        }
        sort(sta+1,sta+top+1);
        int d=INF;
        for(int i=0;i<top;i++) {
            int x=sta[i];
            d=min(d,max(x,(sta[top]-sta[i+1]+1)/2));
        }
        ans=max(ans,d);
        cout<<ans<<'\n';
    }
}