P12380 [蓝桥杯 2023 省 Python B] 管道

题目描述

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

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

对于位于 $L_i$ 的阀门，它流入的水在 $T_i(T_i\ge S_i)$ 时刻会使得从第 $L_i-(T_i-S_i)$ 段到第 $L_i+(T_i-S_i)$ 段的传感器检测到水流。

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

输入格式

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

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

输出格式

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

输入输出样例 #1

输入 #1

3 10
1 1
6 5
10 2

输出 #1

5

说明/提示

评测用例规模与约定

• 对于 $30\%$ 的评测用例，$n\le 200$，$S_i,len\le 3000$；
• 对于 $70\%$ 的评测用例，$n\le 5000$，$S_i,len\le 10^5$；
• 对于所有评测用例，$1\le n\le 10^5$，$1\le S_i,len\le 10^9$，$1\le L_i\le len$，$L_{i-1}<L_i$。

C++实现

#include<iostream>
#include<vector>
using namespace std;
typedef long long ll;
const int N = 1e5 + 7;
int n, len, ans = 2e9 + 1;
int L[N], S[N];
void solve() {
	ll l = 1, r = 2e9 + 1;
	while (l < r) {
		ll mid = (l + r) >> 1;
		ll lp = 0;
		for (int i = 1; i <= n; i++) {
			if (S[i] <= mid) {
				if (lp >= L[i] - (mid - S[i]) - 1) {
					lp = max(lp, L[i] + (mid - S[i]));
				}
			}
			if (lp >= len)break;
		}
		if (lp < len)l = mid + 1;
		else r = mid;
	}
	ans = l;
}
int main() {
	cin >> n >> len;
	for (int i = 1; i <= n; i++) {
		cin >> L[i] >> S[i];
	}
	solve();
	cout << ans << '\n';
	return 0;
}

后续

接下来我会不断用C++来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现，记录日常的编程生活、比赛心得，感兴趣的请关注，我后续将继续分享相关内容