Question

一个数轴，牛牛的家在0点处，在道路上的整数点上建立两个传送门，朋友们可以通过传送门从一个位置瞬间传送到另一个位置，在最优策略下，朋友们最晚需要多长时间可以到达聚会地点？

Solution

答案具有单调性，二分答案。
接下来就是check函数怎么写的问题了。

  1. 牛牛的朋友到0点距离小于等于x的，不用管他们，直接去牛牛家就好了
  2. 其余的求出一个最右端端点ma,求出一个最左端端点mi，当ma-mi<=2*x的时候满足条件可以缩小R。

当时做的时候很蠢，想着二分门的位置，左边二分一次，右边二分一次，被卡了一组数据，也不知道为什么，可能门的位置是没有单调性的吧?
门的位置是一定在ma和mi中间的最接近的整数点上，这道题二分答案更为合理。
还有一点自己有时候写二分的时候会想写成mid=L+(R-L)/2然后又想着改成位运算变成mid=L+(R-L)>>1，但是+的运算优先级是比>>来得高的，所以这样写是错的，要写也只能写成mid=(L+(R-L))>>1，唔实在是太麻烦了。

Code

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int>P;
const double eps = 1e-8;
const int NINF = 0xc0c0c0c0;
const int INF  = 0x3f3f3f3f;
const ll  mod  = 1e9 + 7;
const ll  maxn = 1e6 + 5;
const int N = 1e5 + 5;

ll n,a[N],ans;

bool check(ll x){
    ll ma=-2e9,mi=2e9;
    for(int i=1;i<=n;i++){
        if(abs(a[i])<=x) continue;
        ma=max(ma,a[i]);
        mi=min(mi,a[i]);
    }
    return ma-mi<=2*x;
}

void solve(){
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i];
    int L=0,R=2e9,ans=0,mid;
    while(L<R){
        mid=L+R>>1;
        if(check(mid)) ans=mid,R=mid;
        else L=mid+1;
    }
    cout<<ans<<'\n';
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int T;cin>>T;
    while(T--){
        solve();
    }
    return 0;
}