蓝桥杯2023年第十四届省赛真题-管道

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

对于每个二分出来的时刻，可以将每一个水阀所能检测的范围算出来（若该时刻小于水阀打开的时刻，则该水阀跳过）。此时问题就变成了对于这些所检测出来的范围是否能覆盖整个管道，显然是一个区间合并知识点。将所有区间合并之后，再看看该区间是否能覆盖11~len的位置即可。

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <queue>

#define x first
#define y second

using namespace std;
using ll = long long;
typedef pair<int, int> PII;
const int N = 1e5 + 3;

int n, m; // n表示水阀数量，m表示管道长度
PII w[N], q[N]; // 定义长度为N的水阀数组w，和临时数组q

bool check(int mid)
{
    int cnt = 0; // 初始化计数器为0，用于统计每个水阀的有效区间
    for (int i = 1; i <= n; i++)
    {
        int L = w[i].x, S = w[i].y; // 获取当前水阀的位置L和打开时间S
        if (mid >= S) // 如果mid大于等于水阀打开时间S
        {
            int t = mid - S; // 计算时间差
            int l = max(1, L - t), r = min((ll)m, (ll)L + t); // 计算有效区间的左右边界
            q[cnt++] = {l, r}; // 将有效区间更新到临时数组q中
        }
    }
    sort(q, q + cnt); // 对有效区间进行排序

    int st = -1, ed = -1; // 初始化起点和终点
    for (int i = 0; i < cnt; i++) // 遍历有效的区间
    {
        if (q[i].x <= ed + 1) // 如果当前区间的左边界小于等于前一个区间的右边界+1
            ed = max(ed, q[i].y); // 更新终点
        else
            st = q[i].x, ed = q[i].y; // 否则更新起点和终点
    }
    return st == 1 && ed == m; // 返回有效区间是否覆盖了整个管道
}

int main()
{
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0); // 加速输入输出
    cin >> n >> m; // 读取水阀数量和管道长度
    for (int i = 1; i <= n; i++) // 遍历水阀
        cin >> w[i].x >> w[i].y; // 读取每个水阀的位置和打开时间
    ll l = 0, r = 2e9; // 初始化左边界l为0，右边界r为2e9
    while (l < r) // 二分查找
    {
        ll mid = l + r >> 1; // 计算中点
        if (check(mid)) // 调用函数检查中点是否符合要求
            r = mid; // 更新右边界
        else
            l = mid + 1; // 更新左边界
    }
    cout << r; // 输出结果
    return 0; // 返回0，表示程序执行成功
}