B4096 [CSP-X2022 山东] 独木桥

· · 题解

欢迎报名洛谷网校，期待和大家一起进步！

对于每个站在桥上的人来说，如果不需要碰撞调头，最明智的选择永远是朝向离自己最近的桥头前进。例如，假设某人在距离左端 3 米的位置，而桥总长 10 米，那么他只需 3 秒就能撤离到左端，而无需花费 7 秒跑到右端。

但是实际上，当两个行进方向相反的人相遇时，他们必须调头。但仔细观察会发现，如果忽略他们的身份，这种调头行为的效果等同于两人保持原速"交换身份"继续前进。这就意味着，无论中间发生多少次碰撞，每个人的撤离时间实际上只取决于他们最初的路径选择。

由于所有人同时出发，整个撤离过程的结束时间不取决于平均速度，而是由移动最慢的那个人决定。我们需要找出所有撤离者中最长的个人耗时作为答案即可。

参考代码（只展示关键部分）：

int ans = 0;
for (int i = 0; i < n; i++) {
    // 计算该人离左右两端的较小距离
    int t = (a[i] < L - a[i]) ? a[i] : L - a[i];
    // 更新答案，答案取所有 t 中的最大值
    if (t > ans) ans = t;
}