目录

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

1. 管道

1. 问题描述

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

一开始管道是空的，位于 Li L_iLi​ 的阀门会在 Si S_iSi​ 时刻打开，并不断让水流入管道。

对于位于 Li L_iLi​ 的阀门，它流入的水在 Ti T_iTi​ ( Ti≥ Si T_i \geq S_iTi​≥Si​) 时刻会使得从第 Li− ( Ti− Si)L_i – (T_i – S_i)Li​−(Ti​−Si​) 段到第 Li+ ( Ti− Si)L_i + (T_i – S_i)Li​+(Ti​−Si​) 段的传感器检测到水流。

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

2. 输入格式

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

接下来 nnn 行每行包含两个整数 Li, Si L_i,S_iLi​,Si​，用一个空格分隔，表示位于第 Li L_iLi​ 段管道中央的阀门会在 Si S_iSi​ 时刻打开。

3. 输出格式

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

4. 样例输入

3 101 16 510 2

5. 样例输出

5

6. 评测用例规模与约定

对于 303030% 的评测用例， n ≤ 200n \leq 200n≤200， Si, len ≤ 3000S_i, \text{len} \leq 3000Si​,len≤3000；

对于 707070% 的评测用例， n ≤ 5000n \leq 5000n≤5000， Si, len ≤ 1 05 S_i, \text{len} \leq 10^5Si​,len≤105；

对于所有评测用例， 1 ≤ n ≤ 1 05​1 \leq n \leq 10^5​1≤n≤105​， 1 ≤ Si, len ≤ 1 09​1 \leq S_i,\text{len} \leq 10^9​1≤Si​,len≤109​， 1 ≤ Li≤ len​1 \leq L_i \leq \text{len}​1≤Li​≤len​， L i − 1< Li​L_{i-1} < L_i​Li−1​<Li​​。

2. 解题思路

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

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

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

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

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

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

3. AC_Code

  • C++
#includeusing 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 Falser = v[0][1]for i in range(1, len(v)):if v[i][0] <= r + 1:r = max(r, v[i][1])else:breakreturn r >= ml = 1r = 2_000_000_000while l < r:mid = (l + r) // 2if check(mid):r = midelse:l = mid + 1print(r)