1. 管道

1. 問題描述

有一根長(zhǎng)度為 $\text{len}$ 的橫向的管道，該管道按照單位長(zhǎng)度分為 $\text{len}$ 段，每一段的中央有一個(gè)可開關(guān)的閥門和一個(gè)檢測(cè)水流的傳感器。

一開始管道是空的，位于 $L_i$ 的閥門會(huì)在 $S_i$ 時(shí)刻打開，并不斷讓水流入管道。

對(duì)于位于 $L_i$ 的閥門，它流入的水在 $T_i$ ($T_i\ge S_i$) 時(shí)刻會(huì)使得從第 $L_i?(T_i?S_i)$ 段到第 $L_i+(T_i?S_i)$ 段的傳感器檢測(cè)到水流。

求管道中每一段中間的傳感器都檢測(cè)到有水流的最早時(shí)間。

2. 輸入格式

輸入的第一行包含兩個(gè)整數(shù) $n,\text{len}$，用一個(gè)空格分隔，分別表示會(huì)打開的閥門數(shù)和管道長(zhǎng)度。

接下來 $n$ 行每行包含兩個(gè)整數(shù) $L_i,S_i$，用一個(gè)空格分隔，表示位于第 $L_i$ 段管道中央的閥門會(huì)在 $S_i$ 時(shí)刻打開。

3. 輸出格式

輸出一行包含一個(gè)整數(shù)表示答案。

4. 樣例輸入

3 10
1 1
6 5
10 2

5. 樣例輸出

5

6. 評(píng)測(cè)用例規(guī)模與約定

對(duì)于 $30$% 的評(píng)測(cè)用例，$n\le 200$，$S_i,\text{len}\le 3000$；

對(duì)于 $70$% 的評(píng)測(cè)用例，$n\le 5000$，$S_i,\text{len}\le 10^5$；

對(duì)于所有評(píng)測(cè)用例，$1\le n\le 10^5?$，$1\le S_i,\text{len}\le 10^9?$，$1\le L_i\le \text{len}?$，$L_{i?1}<L_i?$。

2. 解題思路

對(duì)于一個(gè)時(shí)間點(diǎn) $x$，如果此時(shí)所有傳感器都能檢測(cè)到水流，那么當(dāng)時(shí)間點(diǎn)大于 $x$ 時(shí)也一定保證所有傳感器都能檢測(cè)到水流。題目要求我們找到滿足條件的最小時(shí)間點(diǎn)，因?yàn)榇鸢妇哂卸涡?，所以我們可以想到二分答案?/p>

有了二分的思路后，問題轉(zhuǎn)換為對(duì)于一個(gè)確定的時(shí)間點(diǎn) $x$，我們?nèi)绾闻袛啻藭r(shí)所有傳感器都能檢測(cè)到水流？仔細(xì)思考，當(dāng)時(shí)間確定后，對(duì)于一個(gè)位于 $a_i$ 且開啟時(shí)間為 $S_i(S_i\le x)$ 的閥門，它的水流實(shí)際就是一條覆蓋區(qū)間 $[a_i?(x?S_i),a_i+(x?S_i)]$ 的線段。

我們可以將所有 $S_i\le x$ 的閥門都進(jìn)行轉(zhuǎn)換，實(shí)際上得到的就是若干條線段。判斷所有傳感器是否都能檢測(cè)到水流，等價(jià)于判斷能否用這若干條線段覆蓋區(qū)間 $[1,\text{len}]$，問題接著轉(zhuǎn)換為區(qū)間覆蓋問題。

區(qū)間覆蓋是一個(gè)經(jīng)典問題。我們可以按區(qū)間的左端點(diǎn)來排序這些區(qū)間。接下來，我們檢查這些區(qū)間是否覆蓋了整個(gè)管道。如果第一個(gè)區(qū)間的左端點(diǎn)大于 $1$，那么表示管道的開始部分沒有被覆蓋，直接返回 false。否則我們?cè)O(shè)一個(gè)變量 $r$ 表示可到達(dá)的最遠(yuǎn)距離，$r$ 的初始值為第一個(gè)區(qū)間的右端點(diǎn)。我們接著檢查其他區(qū)間是否與 $r$ 相鄰或重疊。如果當(dāng)前區(qū)間和 $r$ 相鄰或重疊，我們將當(dāng)前區(qū)間的右端點(diǎn)和 $r$ 取最大值。最后如果 $r\ge \text{len}$ 則說明成功覆蓋所有區(qū)間，否則說明沒有。

回過頭來考慮如何書寫二分，設(shè) $l$ 為答案的下界，$r$ 為答案的上界，如果二分得到的時(shí)間點(diǎn) $\text{mid}$ 符合條件，因?yàn)榇笥?$\text{mid}$ 的時(shí)間點(diǎn)也一定符合條件，所以更新 $r=\text{mid}$，否則更新 $l=\text{mid+1}$。我們重復(fù)這個(gè)過程，直到搜索范圍的左右端點(diǎn)相等，此時(shí)就找到了最早的時(shí)間。 當(dāng)然 $l,r$ 的初始值我們也需要思考，$l$ 顯然為 $1$，而 $r$ 我們需要考慮極限情況，即只存在一個(gè)最左或最右的閥門在最晚的時(shí)間點(diǎn)打開，顯然此時(shí)需要的時(shí)間為 $2\times 10^9$，所以 $r$ 的初始值為 $2\times 10^9$。

時(shí)間復(fù)雜度：$O(n\log n^2)$。文章來源地址http://www.zghlxwxcb.cn/news/detail-728216.html

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)

到了這里，關(guān)于第十四屆藍(lán)橋杯省賽 Python B 組 D 題——管道（AC）的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！