自动搬运

查看原文

来自洛谷，原作者为

	JIN_LONG super

搬运于2025-08-24 23:15:06，当前版本为作者最后更新于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()