洛谷 P1007 独木桥
先来看题：
P1007 独木桥 - 洛谷
思路分析
为什么这样写
题目里每个士兵速度相同且只能向前走，当两人相遇时“互相转身”，这在本质上等价于他们“互相穿过”，只要我们关心的只是离开桥的时间，不关心具体谁先谁后。
因此可以把每个士兵看成独立的：
- 向左走，离开时间 =
x - 向右走，离开时间 =
L + 1 - x
如何计算
对于每个位置x：
min(distToLeft, distToRight)：表示这个士兵最早可能离开桥的时间max(distToLeft, distToRight)：表示这个士兵最晚可能离开桥的时间
然后：
- 所有士兵最早全部撤离的时间，是这些最优时间中的最大值
- 所有士兵最晚全部撤离的时间，是这些最差时间中的最大值
所以代码里写：
minTime = max(minTime, min(distToLeft, distToRight));maxTime = max(maxTime, max(distToLeft, distToRight));
最后输出minTime maxTime。
为什么这样写是正确的
因为：
- 士兵碰面后转身，不改变“离开桥的时间集合”
- 只需要考虑每个士兵到两端出口的距离
- 不需要模拟复杂的碰撞过程
这就是为什么这个题目可以用简单的max-min逻辑直接求解。
源码部分：
#include <bits/stdc++.h> using namespace std; int main() { int L; if (scanf("%d", &L) != 1) { return 0; } int N; scanf("%d", &N); int minTime = 0; int maxTime = 0; for (int i = 0; i < N; i++) { int x; scanf("%d", &x); int distToLeft = x; int distToRight = L + 1 - x; minTime = max(minTime, min(distToLeft, distToRight)); maxTime = max(maxTime, max(distToLeft, distToRight)); } printf("%d %d\n", minTime, maxTime); return 0; }