AcWing 5407. 管道
原题链接
中等
作者:
无双飞怪
,
2024-04-15 16:22:20
,
所有人可见
,
阅读 1
还是和借教室那道题一样 借教室是求有窟窿的最早时间 这道管道是求没有窟窿(全覆盖)的最早时间
因此道理一样 可以按照时间一点一点i++开始遍历 当找到全覆盖时即为最早的全覆盖的时间
然后优化也一样:可以一点一点i++开始遍历 那么就能够用二分
最好都开long long也行 就像这题不确定没想到会被坑
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int l[N],s[N];
typedef long long LL;
typedef pair<int,int> PII;
long long n,len;
bool check(long long mid)//二分的是时间
{
vector<PII> t;
for(int i=0;i<n;i++)
{
if(s[i]<=mid)//mid时间之前的都能打开(这里不是<=)
t.push_back({l[i]-(mid-s[i]),l[i]+(mid-s[i])});
}
sort(t.begin(),t.end());//区间合并之前先进行排序 pair<int,int> 的排序默认按照第一个first进行排序
//对于pair<int,int>的排序 默认按照first的值进行升序排序 first相同的情况下按照second进行升序排序
//接下来开始区间合并
int st=t[0].first,ed=t[0].second;
for(int i=1;i<t.size();i++)//!!这里注意是i<t.size()而不是i<n
{
if(t[i].first<=ed+1)//这里注意+1
ed=max(ed,t[i].second);//!!!这里千万记得取max
else
{
st=t[i].first,ed=t[i].second;//……@
}
}
//到了这一步只要不计数 都不用再写下一步了
//其实关键在……@这一步 不管记什么个数(如AcWing 803.区间合并) 记得这里最后再多写一步
//但若只是单纯的合并区间则不用再写任何东西
if(st<=1&&ed>=len) return true;//这里注意千万不要写ed>=n!!!
return false;
}
int main()
{
cin>>n>>len;
for(int i=0;i<n;i++)
{
scanf("%d%d",&l[i],&s[i]);
}
long long l=0,r=2e9+10;//假如有一个长度为1e9的管道 在s[i]=1e9时打开 则水流到达1号闸门时 时间为2e9
//特别注意 这里得开long long 因为(1e9+2e9)/2 时1e9+2e9会爆掉
while(l<r)
{
long long mid=l+r>>1;
if(check(mid)) r=mid;//因为求的是最短时间 所以满足条件以后看时间再缩小一下行不行
else l=mid+1;
}
cout<<r;
return 0;
}