题目

思路

• 区间合并
  • 1、按照左端点排序
  • 2、遍历窗口，若窗口非法，继续遍历；否则执行3
  • 3、若是第一个窗口，设定合并结果初值，判断结果左端点是否造成“起点过大”，是，FALSE退出；否则执行4
  • 4、判断合并是否会造成“中间缺失”，是，FALSE退出；否，执行5
  • 5、更新结果右端点
  • 6、判断结果右端点是否造成“终点过小”，是，FALSE退出；否则执行2
  • 7、TRUE退出

代码

#include <bits/stdc++.h>
using namespace std;
#define L first
#define S second
const int N = 1e5 + 10;
const int M = 1e9;
typedef pair<int, int> PII;
typedef long long ll;
PII win[N];
int n, len;
ll mid;
ll getl(PII a)
{
  return (ll)a.L - mid + a.S;
}
ll getr(PII a)
{
  return (ll)a.L + mid - a.S;
}
bool cmp(PII a, PII b)
{
  //[L-T+S,L+T-S]
  return getl(a) < getl(b);
}
bool check()
{
  sort(win + 1, win + n + 1, cmp);

  ll l = 0, r = 0;
  for (int i = 1; i <= n; i++)
  {
    ll nl = getl(win[i]), nr = getr(win[i]);
    if (nl > nr)
      continue; // 无效
    if (r == 0)
    {
      l = nl;
      r = nr;
      if (l > 1)
        return false; // 起点过大，无法覆盖
      continue;
    }
    if (nl - r > 1) // 中间缺少，无法覆盖
      return false;
    r = max(r, nr); // 取大
  }

  if (r < len)
    return false; // 终点过小，无法覆盖
  return true;
}
int main()
{
  ios::sync_with_stdio(0);
  cin.tie(0);

  cin >> n >> len;
  for (int i = 1; i <= n; i++)
  {
    cin >> win[i].L >> win[i].S;
  }
  ll l = 0, r = 2 * M;
  while (l < r)
  {
    mid = l + r >> 1;
    if (check())
      r = mid;
    else
      l = mid + 1;
  }

  cout << l;
}