记得开long long
管道题解(暴力二分+区间合并二分)
本质就是查询一个时间满足所有管道通水的情况,但是这个时间要尽可能的小。
因此本题第一个想到的就是类似于二分的查找第一个出现的值的算法。
模板一套,接下来就是写check函数。
题解1 暴力法(50分)($ON^{2}*logN$)
用一个bool数组维护,每次水管扩散后的长度对应的数组变成1,全部遍历完成后检查bool数组是否全部变成了1。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N = 10e5;
ll n,len;
struct water{
ll index;
ll time;
};
water w[N]; // 存储可以放水的闸
ll st[N];//0表示没水,1表示有水
// 核心代码
bool check(ll x){
// On 算法
// 遍历可以放水的闸
for(ll i=1;i<=n;i++){
// 是管道闸口
// 看和x的关系
if(x-w[i].time>=0){
// 扩散的左右边界
ll l = w[i].index-(x-w[i].time);
ll r = w[i].index+(x-w[i].time);
if(l<1) l=1;
if(r>len) r=len;
for(ll i=l;i<=r;i++)
st[i] = 1;
}
}
// 遍历完成后,看看是否满足条件
for(ll i=1;i<=len;i++){
if(st[i]==0) return false;
}
return true;
}
int main(){
cin >> n >> len; // 可以放水的管道数,总管道数
for(int i=1;i<=n;i++){
cin >> w[i].index >> w[i].time ;
}
// 二分
// 最小时刻为1,最长时刻为10e9
ll l =1,r=2e9;
// 二分查找
while(l<r){
memset(st,0,sizeof(st));
ll mid = (l+r) >> 1; // 男左女右 男1女0
if(check(mid)) // 如果符合要求,要求是全部管道有水
// 此时的mid可能是答案,需要包含进去
r = mid; // 女
else
l = mid+1;// 不符合要求就不需要包含
}
cout << r;
}
题解2(nlognlogn)
使用区间合并,我的代码和yxc不同(其实我也叫yxc),我做区间合并是喜欢将第一个区间进行特判,代码可能更好理解。
// 管道区间合并写法
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> PII;// PII表示区间 或者 记录时间
const ll N = 1e5+20;
PII pipe[N]; // 前一个数是索引,后一个是时间
// 只有n个管道会放水
ll len;// 管道长度
ll n; // 放水的管道个数
bool check(ll mid){
vector <PII> temp;// 临时存储区间
for(ll i=1;i<=n;i++){
// 存放区间
if(mid-pipe[i].second >= 0){
// 注意边界
ll l = pipe[i].first-(mid-pipe[i].second);
ll r = pipe[i].first+(mid-pipe[i].second);
if(l<1) l=1;
if(r>len) r=len;
temp.push_back({l,r});
}
}
// 做区间合并
sort(temp.begin(),temp.end());
vector<PII> res;
// 先把第一个读进来
int st,ed;
st = temp[0].first,ed=temp[0].second;
int flag = 1; // 跳过小技巧
for(auto t:temp){
// 巧妙跳过第一次遍历
if(flag==1){
flag =0 ;
continue;
}
if(ed+1<t.first){ // 如果不能合并,注意假如 1,2 3,4 也是可以合并的 ,所以要加1
res.push_back({st,ed}); // 目的是区分第一次遍历 , 存储的是之间的维护的区间
st = t.first,ed=t.second; // 因为是按照顺序的,前面的区间无法和他合并,后面的都没法合并,那就要更新维护的区间
}
else if(ed+1<=t.second){ // 更新末尾
ed = t.second;
}
else if(ed+1>t.second){
// 不用做任何操作
}
}
res.push_back({st,ed});
if(res.size()==1 && st==1 && ed==len)
return true;
else
return false;
}
int main(){
// 主题模板不变
cin >> n >> len; // 可以放水的管道数,总管道数
for(ll i=1;i<=n;i++){
cin >> pipe[i].first >> pipe[i].second ;
}
// 二分
// 最小时刻为1,最长时刻为10e9
ll l =1,r=2e9;
// 二分查找
while(l<r){
//memset(st,0,sizeof(st));
ll mid = (l+r) >> 1; // 男左女右 男1女0
if(check(mid)) // 如果符合要求,要求是全部管道有水
// 此时的mid可能是答案,需要包含进去
r = mid; // 女
else
l = mid+1;// 不符合要求就不需要包含
}
cout << r ;
}