题解：P12380 [蓝桥杯 2023 省 Python B] 管道

· · 题解

解题思路

题意不用多说，根据题意的话，假如说在 t_i 时刻满足题目要求，那么比 t_i 大的时刻也一定满足要求，所以具有单调性，此时可以想到用二分来做。

对于每个二分出来的时刻，可以将每一个水阀所能检测的范围算出来（若 t_i 时刻小于当前水阀打开的时刻，则该水阀跳过）。

此时问题就变成了这些所检测出来的范围是否能覆盖整个管道，这是一个区间合并。将所有区间合并之后，再看看该区间是否能覆盖 1 到 len 的位置即可。

当然，区间合并就直接将每一个左端点进行排序就行。

#include <bits/stdc++.h>
using namespace std;
//#define int long long 
#define maxn 1000005
#define maxa 1005
#define repr(i,a,b) for(int i = a;i <= b;i++)
#define PII pair<int,int>
//typedef long long ll;
struct node{
    int L,S;
};
int n,len;
vector<node> v;
bool check(int T){
    vector<PII> v1;
    for(auto &wei:v){
        if(wei.S>T) continue;
        int d = T-wei.S;
        int a = wei.L-d;
        int b = wei.L+d;
        a = max(a,1);
        b = min(b,len);
        if(a>b) continue; 
        v1.emplace_back(a,b);
    }
    sort(v1.begin(),v1.end());
    int ans = 0;
    for(auto &p : v1){
        int a = p.first,b = p.second;
        if(a>ans+1){
            return false;
        }
        ans = max(ans,b);
    }
    return ans>=len;
}
signed main(){
    cin.tie(0)->ios::sync_with_stdio(0);
    cout.tie(0);
    cin>>n>>len;
    v.resize(n);
    repr(i,0,n-1){
        cin>>v[i].L>>v[i].S;
    }
    int l=0,r=0;
    for(auto &value:v){
        r = max(r,value.S+max(value.L-1,len-value.L));
    }
    int ans = r;
    while(l<=r){
        int mid = (l+r)>>1;
        if(check(mid)){
            ans = mid;
            r = mid-1;
        } 
        else{
            l = mid+1;
        }
    }
    cout<<ans<<endl;
    return 0;
}