第十四届蓝桥杯省赛 Python B 组 D 题——管道（AC）

清疚 2023-10-15 18:17 17阅读 0赞

#### 目录 ####

*  1. 管道
 *   *  1. 问题描述
     *  2. 输入格式
     *  3. 输出格式
     *  4. 样例输入
     *  5. 样例输出
     *  6. 评测用例规模与约定
 *  2. 解题思路
 *  3. AC\_Code

## 1. 管道 ##

### 1. 问题描述 ###

有一根长度为  len \\text\{len\} len 的横向的管道，该管道按照单位长度分为  len \\text\{len\} len 段，每一段的中央有一个可开关的阀门和一个检测水流的传感器。

一开始管道是空的，位于  L i L\_i Li 的阀门会在  S i S\_i Si 时刻打开，并不断让水流入管道。

对于位于  L i L\_i Li 的阀门，它流入的水在  T i T\_i Ti ( T i ≥ S i T\_i \\geq S\_i Ti≥Si) 时刻会使得从第  L i − ( T i − S i ) L\_i - (T\_i - S\_i) Li−(Ti−Si) 段到第  L i + ( T i − S i ) L\_i + (T\_i - S\_i) Li\+(Ti−Si) 段的传感器检测到水流。

求管道中每一段中间的传感器都检测到有水流的最早时间。

### 2. 输入格式 ###

输入的第一行包含两个整数  n , len n,\\text\{len\} n,len，用一个空格分隔，分别表示会打开的阀门数和管道长度。

接下来  n n n 行每行包含两个整数  L i , S i L\_i,S\_i Li,Si，用一个空格分隔，表示位于第  L i L\_i Li 段管道中央的阀门会在  S i S\_i Si 时刻打开。

### 3. 输出格式 ###

输出一行包含一个整数表示答案。

### 4. 样例输入 ###

3 10
    1 1
    6 5
    10 2

### 5. 样例输出 ###

### 6. 评测用例规模与约定 ###

对于  30 30 30% 的评测用例， n ≤ 200 n \\leq 200 n≤200， S i , len ≤ 3000 S\_i, \\text\{len\} \\leq 3000 Si,len≤3000；

对于  70 70 70% 的评测用例， n ≤ 5000 n \\leq 5000 n≤5000， S i , len ≤ 1 0 5 S\_i, \\text\{len\} \\leq 10^5 Si,len≤105；

对于所有评测用例， 1 ≤ n ≤ 1 0 5 1 \\leq n \\leq 10^5 1≤n≤105， 1 ≤ S i , len ≤ 1 0 9 1 \\leq S\_i,\\text\{len\} \\leq 10^9 1≤Si,len≤109， 1 ≤ L i ≤ len 1 \\leq L\_i \\leq \\text\{len\} 1≤Li≤len， L i − 1 < L i L\_\{i-1\} < L\_i Li−1<Li。

## 2. 解题思路 ##

对于一个时间点  x x x，如果此时所有传感器都能检测到水流，那么当时间点大于  x x x 时也一定保证所有传感器都能检测到水流。题目要求我们找到满足条件的最小时间点，因为答案具有二段性，所以我们可以想到二分答案。

有了二分的思路后，问题转换为对于一个确定的时间点  x x x，我们如何判断此时所有传感器都能检测到水流？仔细思考，当时间确定后，对于一个位于  a i a\_i ai 且开启时间为  S i ( S i ≤ x ) S\_i(S\_i \\leq x) Si(Si≤x) 的阀门，它的水流实际就是一条覆盖区间  \[ a i − ( x − S i ) , a i + ( x − S i ) \] \[a\_i-(x-S\_i),a\_i+(x-S\_i)\] \[ai−(x−Si),ai\+(x−Si)\] 的线段。

我们可以将所有  S i ≤ x S\_i \\leq x Si≤x 的阀门都进行转换，实际上得到的就是若干条线段。判断所有传感器是否都能检测到水流，等价于判断能否用这若干条线段覆盖区间  \[ 1 , len \] \[1,\\text\{len\}\] \[1,len\]，问题接着转换为区间覆盖问题。

区间覆盖是一个经典问题。我们可以按区间的左端点来排序这些区间。接下来，我们检查这些区间是否覆盖了整个管道。如果第一个区间的左端点大于  1 1 1，那么表示管道的开始部分没有被覆盖，直接返回 `false`。否则我们设一个变量  r r r 表示可到达的最远距离， r r r 的初始值为第一个区间的右端点。我们接着检查其他区间是否与  r r r 相邻或重叠。如果当前区间和  r r r 相邻或重叠，我们将当前区间的右端点和  r r r 取最大值。最后如果  r ≥ len r \\geq \\text\{len\} r≥len 则说明成功覆盖所有区间，否则说明没有。

回过头来考虑如何书写二分，设  l l l 为答案的下界， r r r 为答案的上界，如果二分得到的时间点  mid \\text\{mid\} mid 符合条件，因为大于  mid \\text\{mid\} mid 的时间点也一定符合条件，所以更新  r = mid r=\\text\{mid\} r=mid，否则更新  l = mid+1 l=\\text\{mid+1\} l=mid+1。我们重复这个过程，直到搜索范围的左右端点相等，此时就找到了最早的时间。 当然  l , r l,r l,r 的初始值我们也需要思考， l l l 显然为  1 1 1，而  r r r 我们需要考虑极限情况，即只存在一个最左或最右的阀门在最晚的时间点打开，显然此时需要的时间为  2 × 1 0 9 2 \\times 10^9 2×109，所以  r r r 的初始值为  2 × 1 0 9 2 \\times 10^9 2×109。

时间复杂度： O ( n log ⁡ n 2 ) O(n\\log n^2) O(nlogn2)。

## 3. AC\_Code ##

*  C++

#include<bits/stdc++.h>
    using namespace std;
    typedef long long LL;
    #define sz(s) ((int)s.size())
    
    int n, m;
    int main()
    {
        
    	ios_base :: sync_with_stdio(false);
    	cin.tie(0); cout.tie(0);
    	cin >> n >> m;
    	vector<int> a(n), s(n);
    	for (int i = 0; i < n; ++i) {
        
    		cin >> a[i] >> s[i];
    	}
    	auto check = [&](LL t) {
        
    		std::vector<pair<LL, LL>> v;
    		for (int i = 0; i < n; ++i) {
        
    			if (t >= s[i]) v.push_back({
        a[i] - (t - s[i]), a[i] + (t - s[i])});
    		}
    		sort(v.begin(), v.end());
    		if (sz(v) == 0 || v[0].first > 1) return false;
    		LL r = v[0].second;
    		for (int i = 1; i < sz(v); ++i) {
        
    			if (v[i].first <= r + 1) r = max(r, v[i].second);
    			else break;
    		}
    		return r >= m;
    	};
    	LL l = 1, r = 2e9;
    	while (l < r) {
        
    		LL mid = l + r >> 1;
    		if (check(mid)) r = mid;
    		else l = mid + 1;
    	}
    	cout << r << '\n';
    	return 0;
    }

*  Java

import java.util.*;
    
    public class Main {
        
        static int n, m;
    
        public static void main(String[] args) {
        
            Scanner sc = new Scanner(System.in);
            n = sc.nextInt();
            m = sc.nextInt();
            int[] a = new int[n];
            int[] s = new int[n];
            for (int i = 0; i < n; ++i) {
        
                a[i] = sc.nextInt();
                s[i] = sc.nextInt();
            }
            long l = 1, r = 2_000_000_000;
            while (l < r) {
        
                long mid = l + r >>> 1;
                if (check(mid, a, s)) r = mid;
                else l = mid + 1;
            }
            System.out.println(r);
        }
    
        private static boolean check(long t, int[] a, int[] s) {
        
            List<Pair<Long, Long>> v = new ArrayList<>();
            for (int i = 0; i < n; ++i) {
        
                if (t >= s[i]) {
        
                    v.add(new Pair<>(a[i] - (t - s[i]), a[i] + (t - s[i])));
                }
            }
            v.sort(Comparator.comparingLong(Pair::getKey));
            if (v.size() == 0 || v.get(0).getKey() > 1) return false;
            long r = v.get(0).getValue();
            for (int i = 1; i < v.size(); ++i) {
        
                if (v.get(i).getKey() <= r + 1) r = Math.max(r, v.get(i).getValue());
                else break;
            }
            return r >= m;
        }
    
        static class Pair<K, V> {
        
            private final K key;
            private final V value;
    
            public Pair(K key, V value) {
        
                this.key = key;
                this.value = value;
            }
    
            public K getKey() {
        
                return key;
            }
    
            public V getValue() {
        
                return value;
            }
        }
    }

*  Python

n, m = map(int, input().split())
    a = []
    s = []
    for i in range(n):
        a_i, s_i = map(int, input().split())
        a.append(a_i)
        s.append(s_i)
    
    def check(t):
        v = []
        for i in range(n):
            if t >= s[i]:
                v.append((a[i] - (t - s[i]), a[i] + (t - s[i])))
        v.sort()
        if len(v) == 0 or v[0][0] > 1:
            return False
        r = v[0][1]
        for i in range(1, len(v)):
            if v[i][0] <= r + 1:
                r = max(r, v[i][1])
            else:
                break
        return r >= m
    
    l = 1
    r = 2_000_000_000
    while l < r:
        mid = (l + r) // 2
        if check(mid):
            r = mid
        else:
            l = mid + 1
    
    print(r)