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

JIN_LONG · 2025-04-29 17:41:46 · 题解

思路：

这题的思路是用二分答案来猜时间，在输出得到的答案即可，以下是集体步骤。

首先输入，然后进入二分的循环中。
接着就是最重要的检查函数了，在检查函数中枚举 1 到 n，计算水流流经范围，然后给流经的范围做上标记，检查是否全部的传感器是否有水流经过。
代码：

给流经的范围做上标记其实是个难点，以下是 75 分代码，使用的是桶来计数和前缀和，但因为 len 的取值是 10^9，所以爆数组了。

#include <bits/stdc++.h>
using namespace std;
long long n,len;
struct kok{
    long long L,S;
}a[100002];
int cmp(kok x,kok y){
    return x.S<y.S;
}
int check(long long mid){
    int tong[100002];
    for(int i=0;i<=len;i++){
        tong[i]=0;
    }
    for(int i=1;i<=n;i++){
        if(a[i].S<=mid){
            int l=a[i].L-(mid-a[i].S);
            int r=a[i].L+(mid-a[i].S);
            //cout<<mid<<" "<<l<<" "<<r<<endl;
            if(l<0)l=0;
            if(r>len)r=len;
            tong[l]++;
            tong[r+1]--;
        }
        else break;
    }
    for(int i=1;i<=len;i++){
        tong[i]+=tong[i-1];
    }
    int q=1;
    for(int i=1;i<=len;i++){
        if(tong[i]==0)q=0;
    }
    return q;
}
int main(){
    cin>>n>>len;
    for(int i=1;i<=n;i++){
        cin>>a[i].L>>a[i].S;
    }
    sort(a+1,a+1+n,cmp);
    long long l=0,r=1000000000;
    while(l+1<r){
        long long mid=(l+r)/2;
        if(check(mid)){
            r=mid;
        }
        else {
            l=mid;
        }
        //cout<<l<<" "<<r<<endl;
    }
    cout<<r;
    return 0;
}

正确代码要把桶来计数和前缀和改成下面一小段代码来计算检测到水流的传感器的数量。

    sort(b.begin(),b.end());
    int ans=0;
    for(auto p: b){
        int l=p.x,r=p.y;
        if(ans+1<l)
            return false;
        ans=max(ans,r);
    }
    return ans>=m;

以下是 python 代码。

def s():
    import sys
    i=sys.stdin.read
    d=i().split()
    x=0
    n,l=int(d[x]),int(d[x + 1])
    x+=2
    v=[]
    for _ in range(n):
        L, S = int(d[x]), int(d[x + 1])
        v.append((L, S))
        x += 2

    a = 0
    b = 2 * 10**18

    def c(t):
        r = []
        for L, S in v:
            if t >= S:
                d = t - S
                a = L - d
                b = L + d
                a = max(1, a)
                b = min(l, b)
                if a <= b:
                    r.append((a, b))
        if not r:
            return False
        r.sort()
        k = 0
        for a, b in r:
            if a > k + 1:
                return False
            k = max(k, b)
            if k >= l:
                return True
        return k >= l

    ans = b
    while a <= b:
        m = (a + b) // 2
        if c(m):
            ans = m
            b = m - 1
        else:
            a = m + 1
    print(ans)

s()

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

思路：

代码：