题目链接：5407. 管道 - AcWing题库
有一根长度为 len的横向的管道，该管道按照单位长度分为 len段，每一段的中央有一个可开关的阀门和一个检测水流的传感器。
一开始管道是空的，位于 Li的阀门会在 Si 时刻打开，并不断让水流入管道。
对于位于 Li 的阀门，它流入的水在 Ti（Ti≥Si）时刻会使得从第 Li−(Ti−Si)段到第 Li+(Ti−Si) 段的传感器检测到水流。
求管道中每一段中间的传感器都检测到有水流的最早时间。
输入格式
输入的第一行包含两个整数 n,len，用一个空格分隔，分别表示会打开的阀门数和管道长度。
接下来 nn 行每行包含两个整数 Li,Si，用一个空格分隔，表示位于第 Li 段管道中央的阀门会在 Si 时刻打开。
输出格式
输出一行包含一个整数表示答案。
数据范围
对于 30%30% 的评测用例，n≤200，Si,len≤3000；
对于 70%70% 的评测用例，n≤5000，Si,len≤105；
对于所有评测用例，1≤n≤105，1≤Si,len≤109，1≤Li≤len，Li−1<Li。
输入样例：
解释
3 10 1 1 6 5 10 2
输出样例：
5#include<iostream>
#include<algorithm>
#include<cstring>
#include<vector>
using namespace std;const int N = 1e5 + 10; // 定义常量 N，表示数组的最大长度
typedef long long LL; // 定义 long long 类型的别名 LL
typedef pair<int, int> PII; // 定义 pair<int, int> 类型的别名 PIIPII a[N]; // 存储每个水阀的位置和打开时间
int n, len; // n 表示水阀的数量，len 表示管道的长度// 检查是否可以用长度为 x 的检测器覆盖整个管道
bool check(LL x) {vector<PII> segs; // 存储每个水阀所能检测的区间for (int i = 0; i < n; i++) {int l = a[i].first, s = a[i].second; // l 表示水阀的位置，s 表示水阀打开的时间if (s > x) continue; // 若当前时刻小于水阀打开的时刻，则该水阀直接跳过// 计算每个水阀所能检测的范围int left = max(1LL, l - x + s); // 计算左端点int right = min((LL)len, l + x - s); // 计算右端点segs.push_back({left, right});}int cnt = segs.size(); // 获取区间数量if (segs.empty()) return false; // 如果没有可检测的区间，返回 falsesort(segs.begin(), segs.end()); // 按左端点从小到大排序if (segs[0].first > 1) return false; // 如果第一个区间的左端点大于 1，返回 falseint dr = segs[0].second; // 初始化当前检测范围的右端点for (int i = 1; i < cnt; i++) { // 进行区间合并if (segs[i].first > dr + 1) return false; // 如果当前区间的左端点大于上一个区间的右端点加 1，返回 falsedr = max(dr, segs[i].second); // 更新当前检测范围的右端点}return dr == len; // 检查是否覆盖了整个管道
}int main() {scanf("%d%d", &n, &len); // 读取水阀的数量 n 和管道的长度 lenfor (int i = 0; i < n; i++) {int l, s;scanf("%d%d", &l, &s); // 读取每个水阀的位置 l 和打开时间 sa[i] = {l, s}; // 存储水阀的位置和打开时间}LL l = 1, r = 2e9; // 初始化二分查找的左右边界while (l < r) { // 二分查找最小的检测器长度LL mid = l + r >> 1; // 计算中间值 midif (check(mid)) r = mid; // 如果可以覆盖整个管道，则更新右边界else l = mid + 1; // 否则更新左边界}printf("%lld", l); // 输出最小的检测器长度return 0;
}