【管道——二分+区间合并】

题目

思路

• 区间合并
  • 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;elsel = mid + 1;}cout << l;
}