AcWing 5407. 管道
原题链接
中等
作者:
CqAq
,
2024-04-09 19:46:36
,
所有人可见
,
阅读 5
算法1
C++ 代码
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
ll n, len;//最长时间1e9---二分枚举最短时间----时间越长越能完成,具有单调性
typedef pair<ll,ll> pii;
#define x first
#define y second
const int MN = 1E5 + 9;
pii ls[MN], seg[MN];//segment:一段的意思
bool check(ll mid){
int clip = 1;
for(int i = 1; i <= n; ++ i) {
if(ls[i].y > mid) continue;
int le = max(1ll, ls[i].x - (mid - ls[i].y));//位置 - (时间 - 开始时间)
int ri = min(len, ls[i].x + (mid - ls[i].y));//位置 + (时间 - 开始时间)
seg[clip].x = le, seg[clip].y = ri;
clip ++;
}
sort(seg + 1, seg + clip);// 排序以第一关键字升序
//ll rr = -0x3f;
ll rr = seg[1].y;
if(seg[1].x > 1) return false;
//// seg里面有clip个内容
for(int i = 2; i < clip; ++ i){
if(seg[i].x > rr + 1) return false;
rr = max(seg[i].y, rr);
}
return rr == len;
}
int main(){
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
cin >> n >> len;
for(int i = 1; i <= n; ++ i) cin >> ls[i].x >> ls[i].y;
//每次都是水流扩展一个区间,,查看这些区间是否可以连续合并
ll l = 1, r = 2e9 + 10; //二分枚举一个时刻
while(l < r){
ll mid = l + r >> 1;
if(check(mid)) r = mid;
else l = mid + 1;
}
cout << r;
return 0;
}