A. 聚会

Solution

跟出题人的做法不太一样?
我是考虑二分答案, 我们先从小到大排个序
当我们二分一个x时, x是我们的备选答案(即最晚到达时间), 他可能过大, 也可能过小, 我们需要check一下
我们从左往右遍历全部点, 如果当前的点跟 0 点的距离大于 x 且当前还没有建造过传送门, 就必须建造传送门了
否则这个 x 作为上界失去了他的效果。
那么怎么样建造传送门最优呢?肯定是建在 pos = a[i] + x
因为我们是从小到大遍历, 建在数轴的右边可以给后面的其他点做贡献
然后如果出现一个点他到 0 点和 pos 点的距离都大于 x , 就证明 x 太小, 需要适当提高一下上界
否则, 我们就适当减少上界, 直到得到最优的x.
如此, 答案就具备单调性和check的方案

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long long LL;
const int N = 2e5 + 5;
const ll mod = 998244353;
const int DEG = 30;
const double PI = acos(-1.0);
const double eps = 1e-12;
const ll inf = 1e18;
static auto fast_iostream = [](){
  ios::sync_with_stdio(false);
  cout.tie(nullptr);
  return 0;
}();
ll a[N];
int n;
bool check(ll x){
  ll pos = -1e18;
  for(int i = 1; i <= n; i++){
    if(abs(a[i]) > x){
      if(a[i] <= 0){
        if(pos == -1e18){
          pos = a[i] + x;
        }
        else if(abs(a[i] - pos) > x) return false;
      }
      else if(a[i] > 0){
        if(pos == -1e18)
          pos = a[i] + x;
        else if(abs(a[i] - pos) > x) return false;
      }
    }
  }
  return true;
}
int main(){
  int t;
  cin >> t;
  while(t--){
    cin >> n;
    for(int i = 1; i <= n; i++){
      cin >> a[i];
    }
    sort(a + 1, a + 1 + n);
    ll ans = -1;
    ll left = -1e18, right = 1e18;
    while(left <= right){
      ll mid = left + right >> 1;
      if(check(mid)){
        ans = mid;
        right = mid - 1;
      }
      else left = mid + 1;
    }
    cout << ans << "\n";
  }
  return 0;
}