湖北省建设质量安全协会网站微信小程序 购物网站开发

5407. 管道 - AcWing题库

​​​

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

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

对于位于 Li的阀门，它流入的水在 Ti（Ti≥Si）时刻会使得从第 Li−(Ti−Si) 段到第 Li+(Ti−Si) 段的传感器检测到水流。

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

输入格式

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

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

输出格式

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

数据范围

对于 30%30% 的评测用例，n≤200，Si,len≤3000；
对于 70%70% 的评测用例，n≤5000，Si,len≤105；
对于所有评测用例，1≤n≤105，1≤Si,len≤109

输入样例：

3 10
1 1
6 5
10 2

输出样例：

5

我个人认为非常经典的二分+区间合并题目，一定要好好理解这道题。

根据题目，水流会慢慢向两边增加，求满足题目要求的时刻 t ，就容易发现 t 具有单调性，因为 t 越大，水流流通的范围就越大，就可以通过二分找到临界点 t ，每次二次 t 的时候，相当于 t 确定，然后遍历阀门，可以判断 t 时刻此阀门是否开启，未开启则跳过，否则把该阀门水流的范围 left 和 right 记录下来，然后就是典型的区间合并问题，判断是否覆盖1-len的区间。

根据题目，二分过程中可能会爆int ，需要开 long long ， 且二分范围，左端点显然是1，右端点需要2*len，也就是2e9，因为存在len为1e9时，最后时刻才打开最左边或最右边阀门的最坏情况

AC code：

#include <bits/stdc++.h>
using namespace std;
struct s {int l, s;
} arr[100010];int n, len;
int check(int mid) {int cnt = 0;pair<int, int> q[100010];for (int i = 1; i <= n; i++) {if (arr[i].s > mid) continue;int t = mid - arr[i].s;int l = max(1, arr[i].l - t), r = min((long long)len, (long long) arr[i].l + t);q[cnt++] = {l, r};}sort(q, q + cnt);
//	int be = -1, en = -1;
//	for (int i = 0; i < cnt; i++) {
//		if (q[i].first <= en + 1) {
//			en = max(en, q[i].second);
//		} else {
//			be = q[i].first, en = q[i].second;
//		}
//	}
//	return be==1&&en==len;
//	if(q[0].first>0) return 0;
//	if(q[cnt-1].second<len) return 0;int en = q[0].second;if(q[0].first!=1) return 0;for (int i = 1; i < cnt; i++) {if (q[i].first > en + 1) {return 0;} en=max(en,q[i].second);}return en>=len;
}
int main() {cin >> n >> len;for (int i = 1; i <= n; i++) {cin >> arr[i].l >> arr[i].s;}int l = 0, r = 2e9 + 10;while (l < r) {int mid = (long long)l + r >> 1 ;if (check(mid)) r = mid;else l = mid + 1;}cout << l << endl;return 0;
}