AcWing 5407. 管道——大白话解析
原题链接
中等
作者:
z_AC
,
2024-03-11 09:37:06
,
所有人可见
,
阅读 90
/*
经分析发现 这个时间是可以进行二分的,但是右边界是多少呢,假设件l 和 s
都取得最大值 那么只有当右边界为199999999 那么右边界可以是2e9
如果找到一个满足条件的时间点那么之后的时间一定都满足那么就可以进行二分
然后二分完时间之后就要判断所有的阀门在当前时间内是否可以覆盖长度为len的区间
这时候就可以判断每一个在该时刻范围内可以打开的阀门的区间,然后就是区间合并
最后判断是否覆盖即可
*/
#include <bits/stdc++.h>
using namespace std;
#define x first
#define y second
const int N = 100010;
typedef long long LL;
typedef pair<int,int> PII;
PII a[N];
int n,len;
bool check(LL mid)
{
// 记录所有的区间 最后进行区间合并
vector<PII> segs;
for(int i = 0;i < n;i++) {
int l = a[i].x,s = a[i].y;
if(s > mid) continue;
// 取左边界的时候 左边界最小是1 所以与1 取最大值
// 取右边界的时候 右边界最大值是len 所以与len 取最小值
int left = max(1ll,l - mid + s),right = min((LL)len,l + mid - s);
segs.push_back({left,right});
}
int cnt = segs.size();
sort(segs.begin(),segs.end()); // 将左边界进行排序
if(segs.empty()) return false;
if(segs[0].x > 1) return false; // 如果第一个区间都要大于1 就结束
int dr = segs[0].y;
for(int i = 0;i < cnt ;i++) {
if(segs[i].x > dr + 1) return false;
dr = max (dr,segs[i].y);
}
return dr == len;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin>>n>>len;
for(int i = 0;i < n;i++)
{
cin>>a[i].x>>a[i].y;
}
LL l = 0,r = 2e9;
while(l < r) {
LL mid = l + r >> 1;
if(check(mid)) r = mid;
else l = mid + 1;
}
cout<<r<<endl;
return 0;
}