---
title: "管道"
created: 2025-11-28
tags:
  - 算法
---

# 管道

## 题目 [管道](https://www.acwing.com/problem/content/5410/)

![[image-ce9d8bb2.png]]

## 思路分析

![[image-7bf14933.png]]

模型抽象成 一条数轴上 有一些点 这些点都有一个影响范围

影响范围可调节 问取最小多少可以使区间全覆盖

显然用二分写 套答案 如果取小了往大了找 反之亦然 现在二分已经非常熟练了hh

那么现在问题就在于怎么验证我们套的这个答案对不对

有很多种解法 比如像数据范围比较小的时候 我们可以直接暴力枚举 对每一个点的影响范围内的数做标记 最后遍历整个数轴 看是否全被标记过 如：
农田灌溉

还可以从每个其他点（被覆盖的点） 受害者的角度去看

对每个“受害者”找到它最近的两个基站 看它离俩基站的距离是否都大于我们套的这个mid 如果不是 就说明这个点没被覆盖 mid显然取小了 （怎么找最近的两个基站呢
其实又有很多种办法 你可以二分去找 思路如倒垃圾和
学生和导师也可以用双指针去找 有现成的题目 如无线网络）

然后也可以把每个点的影响范围当成一个区间 我们采用区间合并的方式

如果发现有合并不了的情况 说明中间肯定有空缺咯 那直接失败

如果全合并了 再检查一下 它是不是与完整区间长度相同 是就成功 不是就失败

然后发现其实对于暴力的方法又可以用差分优化一下

啧啧啧 一套题已经可以想出这么多种解法了 唉 两个星期的题没白刷hhh

再来分析一下什么情况用哪种呢

暴力的方式显然是适用于数据范围比较小的吧 而且农田灌溉那题有个特点和这题不一样 就是农田灌溉没有时间这个点的限制 它的所有装置是同时启动的
所以完全不需要考虑其他的 直接枚举即可

然后从“受害者”角度看呢 无线网络那题也有个特殊点 它都把牛和基站分开来存了 显然在暗示你什么东西吧 然后它也没有时间这个点的限制

而这道题 它有个时间限制 数据范围又大 暴力一定会超时

时间限制意味着 某个时刻 并不是所有的影响范围都存在 我们用枚举也没办法解决这个问题 那么区间合并很方便的帮我们解决了这个问题 我们对于每次check
都重新构建一个vector存放 已经开启的水阀的影响范围的l和r 只要对这些东西进行合并操作 如何检查 正如上面所说的 如果不能合并就直接false
如果合并完了 再检查是否与完整区间相等 所以这道题用区间合并的关键点就在于 它有个时间限制

然后这题其实对区间合并的模板做了很大变动 其实也告诉我们 没必要死记 这玩意只需要记住合并不合并两个情况应该做什么就行了 万变不离其中

现在终于爽了 10天前就想着把这三道题整理出来 奈何当时还没复习到区间合并

舒服了 算法基础复习完了 这个念头也圆满了

## 代码实现

```cpp
#include<bits/stdc++.h>
using namespace std;
#define endl '\n'

typedef pair<int,int> PII;
typedef long long LL;
const int N=1e5+10;
PII a[N];
LL n,len;

bool check(LL m){
    vector<PII> segs;
    for(int i=1;i<=n;i++){
        int l=a[i].first,s=a[i].second;
        if(s>m) continue; //若当前时刻小于水阀打开的时刻 则该水阀直接跳过
        int left=max(1ll,l-(m-s)),right=min((LL)len,l+(m-s));
        segs.push_back({left,right});
    }
    sort(segs.begin(),segs.end());
    //如果该时间没有开启的水阀(空)则一定无法填满
    //如果第一个区间都没法覆盖最左边(1位置) (能覆盖第一个位置的水阀现在没开) 则一定无法填满
    if(segs.empty() || segs[0].first>1)     return false;
    int covered=segs[0].second;
    for(int i=1;i<segs.size();i++){
        if(segs[i].first>covered+1)     return false; //区间不能合并 说明有空隙 无法填满
        covered=max(covered,segs[i].second);
    }
    return covered==len;
}

int main()
{
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>n>>len;
    for(int i=1;i<=n;i++){
        int l,s;cin>>l>>s;
        a[i]={l,s};
    }

    LL l=1,r=2e9;
    while(l<r){
        LL mid=l+r>>1;
        if(check(mid))  r=mid;
        else    l=mid+1;
    }
    cout<<r<<endl;
    return 0;
}
```

## 同类题型

## 视频讲解

---
⬅️ [[校门外的树|校门外的树]] 🏠 [[00-刷题理模型]] ➡️ [[list|list]]