AcWing 5407. 管道（二分，区间合并）

有一根长度为 $len$ 的横向的管道，该管道按照单位长度分为 $len$ 段，每一段的中央有一个可开关的阀门和一个检测水流的传感器。

一开始管道是空的，位于 $L_i$ 的阀门会在 $S_i$ 时刻打开，并不断让水流入管道。

对于位于 Li 的阀门，它流入的水在 $T_i（T_i\ge S_i）$时刻会使得从第 $L_i-(T_i-S_i)$ 段到第 $L_i+(T_i-S_i)$ 段的传感器检测到水流。
求管道中每一段中间的传感器都检测到有水流的最早时间。

输入格式
输入的第一行包含两个整数 $n,len$，用一个空格分隔，分别表示会打开的阀门数和管道长度。
接下来 $n$ 行每行包含两个整数 $L_i,S_i$，用一个空格分隔，表示位于第 Li 段管道中央的阀门会在 $S_i$ 时刻打开。

输出格式
输出一行包含一个整数表示答案。

数据范围
对于 $30$ 的评测用例，$n\le 200，S_i,len\le 3000$；
对于 $70$ 的评测用例，$n\le 5000，S_i,len\le 10^5$；
对于所有评测用例，$1\le n\le 10^5，1\le S_i,len\le 10^9，1\le L_i\le len，L_i-1<L_i$。

输入样例：

3 10
1 1
6 5
10 2

输出样例：

5

直入正题，首先确定二分的范围。
最小的时刻就是0时刻，那么l就为0
最大的时刻就是在1e9时刻开阀门，并且只开一个，管道长度也为1e9，则会消耗2e9的时间，那么r就为2e9

并且肯定是时间越长越容易灌满水，则时间越靠右就越容易满足条件，假如在mid时刻。

• 如果满足条件，那么就去搜更短时间，也就是从$lmid$搜
• 如果不满足条件，那么就去搜更长的时间，也就是从$mid+1r$搜

在这里对于验证每个管道是否灌满的方法使用区间合并。
代码中也有详细注解。

代码：

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
#define PII pair<int,int>
const int N = 1e5 + 10;

int n, m;
int s[N], len[N];
vector<PII>q;	//存所有的区间

bool check(int mid) {
	q.clear();	//每次都要初始化
	for (int i = 0; i < n; i++) {
		if (s[i] <= mid) {		//如果没有超过mid时刻（mid时刻之后发生的不算）
			int t = mid - s[i];	//根据公式算出区间

			//这里取max和min，避免超出给出的管道长度的范围
			int l = max(1, len[i] - t), r = min((long long)m, (long long)len[i] + t);
			q.push_back({ l,r });	//压入
		}
	}

	sort(q.begin(), q.end());		//排序

	int st = -1, ed = -1;			//st存最终起点，ed存最终终点
	for (auto t : q) {				//遍历q
		if (t.first <= ed + 1)ed = max(ed, t.second);	//如果当前区间的起点小于等于ed+1，那么就说明起点在st到ed之间，则合并两个区间
		else st = t.first, ed = t.second;	//如果当前区间的起点大于ed+1，即当前区间超出了st到ed之间，则更新区间
		//注意此处为何直接覆盖了st和ed：
		//		在sort之后，所有的元素按照first排序，也就是说现在的元素都是按照起点从小到大排序的
		//		如果这里出现了一个区间的起点大于了ed+1，那么就说明之后的所有区间都不会和当前的区间
		//		有交集了，那么现在的st和ed围成的区间就一定不可能做到覆盖整段管道
	}

	return st == 1 && ed == m;		//如果能够覆盖整段管道，则返回true
}

int main() {
	cin >> n >> m;
	for (int i = 0; i < n; i++)cin >> len[i] >> s[i];

	//二分求最小时刻
	int l = 0, r = 2e9;
	while (l < r) {
		int  mid = (long long)l + r >> 1;
		if (check(mid)) r = mid;
		else l = mid + 1;
	}

	cout << r;
	return 0;
}