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

jur10n · 2025-05-23 14:41:45 · 题解

简单思路

二分答案基础题，直接二分枚举最短的时间。

然后进行检验：直接让所有水龙头放水，看看是否满足淹没了整个管道。

如果满足，继续找更小的解；反之往大找可行解。

代码实现

注意检验部分有一处细节，当前水龙头的范围更大才更新最远点，要取新范围和历史最远的较大值。

#include<bits/stdc++.h>
#define N 100005
using namespace std;

class Quick_IO
{
  public:
    template<typename T>
    void read(T &r)
    {
        T x = 0, f = 1;
        char ch = getchar();
        while (ch < '0' || ch > '9')
        {
            if (ch == '-') f = -1;
            ch = getchar();
        }
        while (ch >= '0' && ch <= '9') x = x * 10 + ch - '0', ch = getchar();
        r = x * f;
    }
    template<typename T, typename... Args>
    void read(T &tmp, Args &... tmps)
    {
        read(tmp);
        read(tmps...);
    }
} io;

int n, len;
int l[N], s[N];

bool Judge(int aim) //检验
{
    int far = 0;
    for (int i = 1, z, y; i <= n; i++)
    {
        if (aim < s[i]) continue;
        z = l[i] - (aim - s[i]);
        y = l[i] + (aim - s[i]);
        if (z - 1 <= far) far = max(y, far); //注意这里需要比较一下
    }
    return far >= len;
}

signed main()
{
    io.read(n, len);
    for (int i = 1; i <= n; i++) io.read(l[i], s[i]);

    int L = 1, R = 1e9, mid = 0, ans = 1e9;
    while (L <= R)  //二分答案
    {
        mid = L + (R - L) / 2;
        if (Judge(mid)) ans = mid, R = mid - 1;
        else L = mid + 1;
    }
    cout << ans;
}