目录
- 1. 管道
- 1. 问题描述
- 2. 输入格式
- 3. 输出格式
- 4. 样例输入
- 5. 样例输出
- 6. 评测用例规模与约定
- 2. 解题思路
- 3. AC_Code
1. 管道
1. 问题描述
有一根长度为 的横向的管道,该管道按照单位长度分为 段,每一段的中央有一个可开关的阀门和一个检测水流的传感器。
一开始管道是空的,位于 的阀门会在 时刻打开,并不断让水流入管道。
对于位于 的阀门,它流入的水在 () 时刻会使得从第 段到第 段的传感器检测到水流。
求管道中每一段中间的传感器都检测到有水流的最早时间。
2. 输入格式
输入的第一行包含两个整数 ,用一个空格分隔,分别表示会打开的阀门数和管道长度。
接下来 行每行包含两个整数 ,用一个空格分隔,表示位于第 段管道中央的阀门会在 时刻打开。
3. 输出格式
输出一行包含一个整数表示答案。
4. 样例输入
3 10
1 1
6 5
10 2
5. 样例输出
5
6. 评测用例规模与约定
对于 % 的评测用例,,;
对于 % 的评测用例,,;
对于所有评测用例,,,,。
2. 解题思路
对于一个时间点 ,如果此时所有传感器都能检测到水流,那么当时间点大于 时也一定保证所有传感器都能检测到水流。题目要求我们找到满足条件的最小时间点,因为答案具有二段性,所以我们可以想到二分答案。
有了二分的思路后,问题转换为对于一个确定的时间点 ,我们如何判断此时所有传感器都能检测到水流?仔细思考,当时间确定后,对于一个位于 且开启时间为 的阀门,它的水流实际就是一条覆盖区间 的线段。
我们可以将所有 的阀门都进行转换,实际上得到的就是若干条线段。判断所有传感器是否都能检测到水流,等价于判断能否用这若干条线段覆盖区间 ,问题接着转换为区间覆盖问题。
区间覆盖是一个经典问题。我们可以按区间的左端点来排序这些区间。接下来,我们检查这些区间是否覆盖了整个管道。如果第一个区间的左端点大于 ,那么表示管道的开始部分没有被覆盖,直接返回 false
。否则我们设一个变量 表示可到达的最远距离, 的初始值为第一个区间的右端点。我们接着检查其他区间是否与 相邻或重叠。如果当前区间和 相邻或重叠,我们将当前区间的右端点和 取最大值。最后如果 则说明成功覆盖所有区间,否则说明没有。
回过头来考虑如何书写二分,设 为答案的下界, 为答案的上界,如果二分得到的时间点 符合条件,因为大于 的时间点也一定符合条件,所以更新 ,否则更新 。我们重复这个过程,直到搜索范围的左右端点相等,此时就找到了最早的时间。 当然 的初始值我们也需要思考, 显然为 ,而 我们需要考虑极限情况,即只存在一个最左或最右的阀门在最晚的时间点打开,显然此时需要的时间为 ,所以 的初始值为 。
时间复杂度:。
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)
文章出处登录后可见!