你在一个向右延申的无限坐标轴上，且你初始在坐标 \(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;
}