牛客挑战赛39 - 聚会 题解

题意

一条数轴上有 个点，设两个传送门，可互相瞬间传送，求这 个点移动到原点最短时间。

算法（）

二分答案，一个传送门必定设在原点，另一个传送门可覆盖 的区域，线性判定答案可行性。

代码

#include <cstdio>
#include <algorithm>

using namespace std;

int t, n, x[100000];
int l, r, mid;

bool check(int ans) {
  int pos = -2e9;
  for (int i = 0; i < n; ++i)
    if (pos == -2e9) {
      if (abs(x[i]) > ans) pos = x[i] + ans;
    } else {
      if (abs(x[i]) > ans && abs(x[i] - pos) > ans) return 0;
    }
  return 1;
}

int main() {
  scanf("%d", &t);
  while (t--) {
    scanf("%d", &n);
    for (int i = 0; i < n; ++i) scanf("%d", &x[i]);
    sort(x, x + n);
    l = 0;
    r = max(-x[0], x[n - 1]);
    while (l < r) {
      mid = (l + r) >> 1;
      if (check(mid))
        r = mid; else
        l = mid + 1;
    }
    printf("%d\n", l);
  }
  return 0;
}