AcWing 5407. 管道(二分+区间和并)
原题链接
中等
作者:
萧_7
,
2024-03-17 23:34:41
,
所有人可见
,
阅读 12
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> PII;
const int N=1e5+10;
PII w[N];
int n,m;
int check(int mid)
{
//int cnt=0;
vector<PII> q;
for(int i=0;i<n;i++)
{
int l=w[i].first,r=w[i].second;
if(r<=mid)//如果开阀时间快
{
int t=mid-r;//已经多出的时间
int L=max(1,l-t),R=min((ll)m,(ll)l+t);//判断覆盖的区间
q.push_back({L,R});//把区间记下
}
}
sort(q.begin(),q.end());//区间排序
int st=q[0].first,ed=q[0].second;
for(auto t:q)
{
if(t.first<=ed+1)ed=max(ed,t.second);//如果有交集合并
//else st=t.first,ed=t.second;//否则,更新区间
}
return st==1&&ed==m;
}
int main()
{
cin>>n>>m;
for(int i=0;i<n;i++)
cin>>w[i].first>>w[i].second;
int l=1,r=2e9;
while(l<r)//二分,判断这个时间能否覆盖完整个区间,如果能,则区间向左缩
{
int mid=(ll)l+r>>1;
if(check(mid))r=mid;
else l=mid+1;
}
cout<<l<<endl;
return 0;
}