洛谷 P1007 独木桥

先来看题P1007 独木桥 - 洛谷思路分析为什么这样写题目里每个士兵速度相同且只能向前走当两人相遇时“互相转身”这在本质上等价于他们“互相穿过”只要我们关心的只是离开桥的时间不关心具体谁先谁后。因此可以把每个士兵看成独立的向左走离开时间 x向右走离开时间 L 1 - x如何计算对于每个位置xmin(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; }