AcWing 5407. 管道
原题链接
中等
作者:
隐灵
,
2024-04-09 19:23:22
,
所有人可见
,
阅读 2
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1e5 + 10;
typedef pair<int, int> PII;
typedef long long LL;
#define x first
#define y second
int n, m; //m表示len
PII w[N], q[N]; //w存初始的每个管道的l,s,q来表示二分之后区间对应的左右端点
bool check(int mid)
{
int cnt = 0; //表示打开在mid时刻之前即mid时刻阀门的数量
for (int i = 0; i < n; i ++ ) //枚举所有阀门,将l,s取出来
{
int L = w[i].x, S = w[i].y; //L表示阀门的位置,S表示阀门打开的时刻
if (S <= mid) //判断一下,如果打开阀门在mid的前面或者mid的时刻
{
int t = mid - S; //算一下距离S经历了多长时间
int l = max(1, L - t), r = min((LL)m, (LL)L + t); //求一下左右端点
q[cnt ++ ] = {l, r};
}
}
sort(q, q + cnt); //按左端点排序
int st = -1, ed = -1;
for (int i = 0; i < cnt; i ++ )
if (q[i].x <= ed + 1) ed = max(ed, q[i].y);
else st = q[i].x, ed = q[i].y;
return st == 1 && ed == m;
}
int main()
{
scanf("%d%d",&n, &m);
for (int i = 0; i < n; i ++ ) scanf("%d%d", &w[i].x, &w[i].y); //读入所有阀门
int l = 0, r = 2e9;
while (l < r) //判断在哪一个时刻检测到全部有水
{
int mid = (LL)l + r >> 1;
if (check(mid)) r = mid;
else l = mid + 1;
}
printf("%d\n", r);
return 0;
}