第十四届蓝桥杯省赛 Python B 组 D 题——管道（AC）
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<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(nlog 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)