526互联

Codeforces Round 895 (Div. 3) B. The Corridor or There and Back Again

发布时间 2023-10-16 20:02:34作者: zsxuan

你在一个向右延申的无限坐标轴上，且你初始在坐标 \(1\) 。有 \(n\) 个陷阱在坐标轴上，第 \(i\) 个陷阱坐标为 \(d_i\) ，且会在你踩上这个陷阱的 \(s_i\) 秒过后发动。这时候你不能进入坐标 \(d_i\) 或者走出坐标 \(d_i\) 。

你需要确定最远的 \(k\) ，保证你能够走到坐标 \(k\) ，并且顺利返回坐标 \(1\) 。

两个思维：

一：不难想到 \(k\) 可以二分，只需要检查返回途中是否遇到阻碍即可。回程路上经过第 \(i\) 个陷阱时的时间为 \(t_i = (k - 1) + (k - d_i)\) ，第 \(i\) 个陷阱启动的时间为 \(ed_i = d_i - 1 + s_i\) 。保证 \(t_i < ed_i\) 即可。

view1 
#include <bits/stdc++.h>
typedef long long ll;
void solve(){
	int n; std::cin >> n;
	std::vector<int> d(n+1), s(n+1);
	for (int i = 1; i <= n; i++) {
		std::cin >> d[i] >> s[i];
	}
	int L = 0 - 1, R = 300 + 1; // 最远可走 200 + 100
	auto check = [&](int x) {
		int ok = 1;
		for (int i = 1; i <= n; i++) {
			if (d[i] > x) continue; // 没触发的陷阱不用计算
			int t = (x - 1) + (x - d[i]), ed = (d[i] - 1 + s[i]);
			ok &= (t < ed);
		}
		return ok;
	};
	while ( R - L > 1 ) {
		int M = ( R + L ) >> 1;
		if ( check(M) )
			L = M; // L
		else
			R = M;
	}
	std::cout << L << '\n';
}
int main() {
	int _ = 1; std::cin >> _;
	while (_--) {solve();}
	return 0;
}

二：进一步思考发现，是否真的需要二分？
\(n\) 个陷阱对应了 \(n\) 个约束条件。
若触发第 \(i\) 个陷阱，则只需在 \(s_i - 1\) 秒内回到 \(d_i\)， 即可以走到的最远距离为 \(l_i = d_i + \lfloor \frac{s_i - 1}{2} \rfloor\) 。最终答案为 \(min_{i = 1}^{n} l_i\) 。

view2 
#include <bits/stdc++.h>
typedef long long ll;
void solve(){
	int n; std::cin >> n;
	std::vector<int> d(n+1), s(n+1);
	int ans = 1 << 30;
	for (int i = 1; i <= n; i++) {
		std::cin >> d[i] >> s[i];
		ans = std::min(ans, d[i] + (s[i] - 1) / 2);
	}
	std::cout << ans << '\n';
}
int main() {
	int _ = 1; std::cin >> _;
	while (_--) {solve();}
	return 0;
}