AcWing 5407. 管道 二分+区间合并
原题链接
中等
作者:
一塌糊涂
,
2024-03-14 12:18:51
,
所有人可见
,
阅读 17
cpp 二分+区间合并
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
using PII = pair<int,int>;
int n,len;
const int N = 1e5+10;
vector<PII> ss;
bool check(int mid){
vector<PII> edge;
for(int i=0;i<ss.size();i++) {
if(ss[i].first<=mid) {
//要开longlong Li−(Ti−Si),Li+(Ti−Si)会爆int
int left = max(1ll,(long long)ss[i].second-(mid-ss[i].first));
int right = min((long long)len,(long long)ss[i].second+(mid-ss[i].first));
edge.push_back({left,right});
}
else break;
}
sort(edge.begin(),edge.end());
if(edge.size()==0 || edge[0].first > 1) return false;
int x = edge[0].first;
int y = edge[0].second;
for(int i=1;i<edge.size();i++) {
if(edge[i].first -1> y) return false;
y = max(y,edge[i].second);
}
return y == len;
}
int main(){
scanf("%d%d", &n, &len);
for(int i=1;i<=n;i++) {
int a,b;
scanf("%d%d", &a, &b);
ss.push_back({b,a});
}
sort(ss.begin(),ss.end());
long long l=1,r=2e9;
while(l<r){
int mid = (l+r)>>1;
if(check(mid)) r = mid;
else l = mid+1;
}
cout<<r<<endl;
return 0;
}