目录
- 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. 样例输出
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
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
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 a(n), s(n); for (int i = 0; i < n; ++i) {cin >> a[i] >> s[i]; } auto check = [&](LL t) {std::vector - 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- 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)
- Python
- Java
- C++