问题描述
有一根长度为 lenlen 的横向的管道，该管道按照单位长度分为 lenlen 段，每一段的中央有一个可开关的阀门和一个检测水流的传感器。
一开始管道是空的，位于 LiLi 的阀门会在 SiSi 时刻打开，并不断让水流入管道。
对于位于 LiLi 的阀门，它流入的水在 TiTi (Ti≥SiTi≥Si) 时刻会使得从第 Li−(Ti−Si)Li−(Ti−Si) 段到第 Li+(Ti−Si)Li+(Ti−Si) 段的传感器检测到水流。
求管道中每一段中间的传感器都检测到有水流的最早时间。
输入格式
输入的第一行包含两个整数 n,lenn,len，用一个空格分隔，分别表示会打开的阀门数和管道长度。
接下来 nn 行每行包含两个整数 Li,SiLi,Si，用一个空格分隔，表示位于第 LiLi 段管道中央的阀门会在 SiSi 时刻打开。
输出格式
输出一行包含一个整数表示答案。
样例输入
3 10
1 1
6 5
10 2
样例输出
5
评测用例规模与约定
对于 3030% 的评测用例，n≤200n≤200，Si,len≤3000Si,len≤3000；
对于 7070% 的评测用例，n≤5000n≤5000，Si,len≤105Si,len≤105；
对于所有评测用例，1≤n≤1051≤n≤105，1≤Si,len≤1091≤Si,len≤109，1≤Li≤len1≤Li≤len，Li−1<LiLi−1<Li。
#include<iostream>
#include<vector>
#include<algorithm>
#include<climits>
using namespace std;
//二分猜时间+逐一检验是否覆盖整条管道(求每一次开水后的区间，然后排序)
//终于在九点多百分之百通过（哭）
//细节很多，尤其是关于数组，还有
struct boon {//开阀的管道int l;int s;
};
int n, len;
vector<boon> kai;
bool check(long long t) {//这里要改成long long，保持统一vector<pair<long, long>> guanzi;long long left;long long right;for (int i = 1; i <= n; i++) { if (t >= kai[i].s) {left = kai[i].l - (t - kai[i].s);right = kai[i].l + (t - kai[i].s);guanzi.push_back({ left,right });//注意写法}}//遍历得到区间if (guanzi.size() == 0) return false;//忽略了为空直接跳出sort(guanzi.begin(), guanzi.end());//不能+n,可能有的管道没有开，没有被放入if (guanzi[0].first > 1) {return false;}//第一个没灌水直接跳出else {long long start = guanzi[0].first;long long end = guanzi[0].second;for (int i = 1; i < guanzi.size(); i++) {//不是nif (guanzi[i].first - end>=2) {//[1,3][4,6]是满足的，不能用guanzi[i].first>endreturn false;}///有间隙，没重合else {if (guanzi[i].second > end)end = guanzi[i].second;}//重合了进行合并}if (start <= 1 && end >= len){return true;}else { return false; }}
}
int main() {cin >> n >>len;kai.resize(n + 2);for (int i = 1; i <= n; i++) { cin >> kai[i].l >> kai[i].s; }long long ltime = 0;long long rtime = INT_MAX;//时间的区间，rtime可以是2e9while (ltime < rtime) {long long mid = (ltime + rtime) / 2;//long long 防止溢出if (check(mid)) {//全覆盖rtime = mid;}else {//未覆盖ltime = mid + 1;}}cout << ltime;return 0;
}
