AcWing 5407. 管道
原题链接
中等
作者:
Jerry_8
,
2024-03-05 15:28:00
,
所有人可见
,
阅读 22
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#define x first
#define y second
using namespace std;//用二分时间遍历,注意时间最长是最晚开闸门时间+漫过的消耗总时长
const int N= 1e5+ 10;
typedef long long LL;
typedef pair<int, int> PII;
int n, len;
PII t[N], w[N];
bool check(int s)
{
int cnt= 0;//进入w是只有进入if语句才需要
for(int i= 0; i< n; i++)
{
int L= t[i].x;
int R= t[i].y;
if(s>= R)//当前时刻大于开阀门时间
{
int dis= s- R;
int by= max(1, L- dis);
int gl= min((LL)len, (LL)L+ dis);
w[cnt++]= {by, gl};
}//w对应时刻这个阀门覆盖的区间
}
//转化成区间合并问题,注意这个是离散的,只要末尾加一等于另一个开头就可以合并
sort(w, w+ cnt);
int a= -1;
int b= -1;
for(int i= 0; i< cnt; i++)
{
if(w[i].x<= b+ 1)
{
b= max(b, w[i].y);//有可能是完全覆盖,所以要取更大的
}
else
{
a= w[i].x;
b= w[i].y;
}
}
return a== 1&& b== len;
}
int main()
{
cin>> n>> len;
for(int i= 0; i< n; i++)
{
scanf("%d%d", &t[i].x, &t[i].y);
}
LL l= 0;
LL r= 2e9+ 10;
while(l< r)//遍历正好这个时刻覆盖所有的时间,如果覆盖说明时间晚了,要遍历左面的,成功动r为右的二分公式
{
int mid= (LL)l+ r>> 1;//超过1e9小心爆int
if(check(mid)) r= mid;
else l= mid+ 1;
}
printf("%lld",r);
return 0;
}