Haokee Note

CF1941F Rudolf and Imbalance

3 min read

二分

我们发现答案具有单调性，因为尝试的答案越大满足条件的概率就越高，因此考虑二分。那么，如何判断 能不能成为一个正确的答案呢？首先， 不能大于 ，因为我们这里只允许添加一个 。然后，不能有两个 满足 ，原因跟上一个一样。然后就是判断的部分了，如果 不满足条件，那么答案就一定区间 里面，因此我们枚举 ，然后再二分一个满足条件的 就行了。注意 需要排序。

#include <iostream>
#include <algorithm>
 
using namespace std;
 
const int kMaxN = 2e5 + 5;
 
int a[kMaxN], d[kMaxN], f[kMaxN], t, n, m, k, ans;
 
bool check(int x) {
  int cnt = 0, mn, mx, b = 0;
  for (int i = 2; i <= n; i++) {
    if (a[i] - a[i - 1] > x) {
      mn = a[i] - x;
      mx = a[i - 1] + x;
      b |= a[i] - a[i - 1] > x * 2;
      cnt++;
    }
  }
  if (cnt > 1 || b) {
    return 0;
  } else if (!cnt) {
    return 1;
  }
  for (int i = 1; i <= m; i++) {
    int p = lower_bound(f + 1, f + k + 1, mn - d[i]) - f;
    if (p != k + 1 && d[i] + f[p] >= mn && d[i] + f[p] <= mx) {
      return 1;
    }
  }
  return 0;
}
 
int main() {
  for (cin >> t; t; t--) {
    cin >> n >> m >> k;
    for (int i = 1; i <= n; i++) {
      cin >> a[i];
    }
    for (int i = 1; i <= m; i++) {
      cin >> d[i];
    }
    for (int i = 1; i <= k; i++) {
      cin >> f[i];
    }
    sort(f + 1, f + k + 1);
    for (int l = 0, r = 2e9; l <= r;) {
      int mid = (l + r) >> 1;
      if (check(mid)) {
        ans = mid, r = mid - 1;
      } else {
        l = mid + 1;
      }
    }
    cout << ans << '\n';
  }
  return 0;
}

Graph View