AcWing 5407. 管道
原题链接
中等
作者:
神的在场证明
,
2024-04-11 17:27:58
,
所有人可见
,
阅读 1
样例
/*
后天蓝桥杯 时隔一个月决定 把之前写过的每日一题重新写一遍, 发现也不是那么容易 到现在才算完成两道, 主要是细节问题 整体思路感觉没问题
这个要注意的点 1、二分时右端点r 要取2e9 因为最慢时第1e9 段管道 在1e9时刻开始 故为 2e9
2、管道最小为1
3 会爆int
思路为 先二分取出那个可能满足的时间, 时间越长,管道中的水 随时间增加一定会满,管道必可满足条件, 故要找可满足条件的最小时间
在check()函数中 会用到区间合并 按题意将待查找的时间带入 求出两段管道位置,将所有的位置的两端的管道合并 看最后能否合成一个长度
大于等于len的管道
*/
#include<iostream>
#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;
#define int long long
const int N = 1e5 + 10;
typedef pair<int,int>pII;
int n, len; //阀门数、管道长度
int l[N], s[N]; //第l段管道 在s刻会打开
//区间合并
void merge(vector<pII> & tube){
sort(tube.begin(), tube.end()); //将带合并的区间排序
int st = -2e9, ed = -2e9; //边界 负无穷
vector<pII> res; //存合并后的管道
for(auto it : tube){
if(ed + 1 < it.first ){ //连续相邻的两段 也可合并 如 (1,3),(4,7)--> (1,7)
if(st != -2e9) res.push_back({st,ed}); //特判 是否为第一次
st = it.first;
ed = it.second;
}else{
ed = max(ed,it.second); //合并区间
}
}
if(st != -2e9) res.push_back({st,ed}); //最后一段
tube = res;
}
//判断 第 x 时刻 水能否填满整个管道
bool check(int x){
vector<pII> tube; //存某时刻谁能达到的左右两端
for(int i = 0; i < n; i++){
if(x < s[i]) continue; //还为达到 能填到该位置左右两端位置的时刻
int f1 = max((long long)1, l[i] - x + s[i]); //该位置 水能达到的左端点
int f2 = min((long long)len, l[i] + x - s[i]);// 该位置 水能达到的右端点
tube.push_back({f1,f2});
}
merge(tube);
if(tube.size() == 1 && tube.back().second == len && tube.front().first == 1) return true; //该时刻水能填满整个管道
return false;
}
signed main(){
scanf("%d %d", &n, &len);
for(int i = 0; i < n; i++) scanf("%d %d", &l[i], &s[i]);
int left = 0, right = 2e9; //二分寻找能满足条件的最早时刻
while(left < right){
int mid = left + right >> 1;
if(check(mid)) right = mid;
else left = mid + 1;
}
printf("%d\n", left);
return 0;
}