题目描述
(二分 + 区间合并)
样例
blablabla
C++ 代码
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
vector<vector<int>> w;
int n, m;
bool check(LL mid) {
vector<vector<int>> segs;
for (int i = 0; i < n ; i ++ ) {
int L = w[i][0], S = w[i][1];
if (S <= mid) { // 当前的时刻大于水闸打开的时刻,此时改水闸已经打开
// 当前水闸可以检测到的范围
int t = mid - S;
int l = max(1, L - t), r = min((LL)L + t, (LL)m); //这里也注意long long, int可能爆
segs.push_back({l, r});
}
}
sort(segs.begin(), segs.end()); //默认按左端点排序
int ed = -1, st = -1;
for(int i = 0; i < segs.size(); i ++) // 将所有水闸可以检测到的范围进行区间合并
{
if (segs[i][0] <= ed + 1) ed = max(ed, segs[i][1]);
else st = segs[i][0], ed = segs[i][1];
}
return ed == m && st == 1;
}
int main() {
cin >> n >> m; // 砸门数和管道数
for (int i = 0; i < n; i ++ ) {
int l, s;
cin >> l >> s;
w.push_back({l, s});
}
LL l = 0, r = 2e9;
while (l < r) { //二分查找最短时间
int mid = (LL) l + r >> 1; //用int可能会爆,记得使用long long
if (check(mid)) r = mid;
else l = mid + 1;
}
cout << r ;
return 0;
}