本题解提供一种简单易懂的check函数,其他部分参考代码,不做过多解释
check函数:
由于输入时阀门位置L已经按升序排列,那么我们考虑直接遍历n个阀门,通过一个变量le保存目前还未检测到水流的最左点,初始为1;
遍历的过程中,分情况:
1、如果le在当前阀门的左侧,查看当前阀门的水是否能到le点,如果可以,将le更新为:当前阀门向右侧流水的最远位置+1
为什么可以这样呢?
大白话分析:当前阀门之前的所有阀门的水都没法到达le,那么它们往右流水传播的进度一定比不过当前阀门
2、如果le在当前阀门的右侧也是同理,省略解释
希望对大家有所帮助
C++ 代码
#include<bits/stdc++.h>
using namespace std;
int n;
long long len,s[100010],l[100010],T;
bool check(long long t){
long long le=1;
for(int i=1;i<=n;i++){
if(l[i]<=le){
if(le-l[i]<=t-s[i]){
le=l[i]+t-s[i]+1;
}
}
else{
if(l[i]-le<=t-s[i]){
le=t-s[i]+l[i]+1;
}
}
}
if(le>len) return true;
else return false;
}
int main(void){
cin>>n>>len;
for(int i=1;i<=n;i++){
cin>>l[i]>>s[i];
}
T=2*(1e9);
long long le=0,ri=T;
while(le<ri){
long long mid=(le+ri)>>1;
if(check(mid)){
ri=mid;
}
else le=mid+1;
}
cout<<le<<endl;
return 0;
}