题意
\(N\) 个人在长度为 \(L\) 独木桥上走动,桥上的坐标为 \(1, 2, \cdots, L\) ,你不知道他们的方向。他们的速度都为 \(1\) 。
- 当两个人相遇时,他们就分别转身,继续行走。(转身不花费时间)
- 当某人来到 \(0\) 或 \(L + 1\) 的位置,他就离开了独木桥。
给定 \(N\) 、 \(L\) 和 \(N\) 个人的位置 \(A_i\) ,求所有人离开独木桥花费的最少时间和最多时间。
思路
首先,所有士兵等价,所以两士兵撞上相当于两人**穿过对方然后再走一步 **
但是,可以有多个人同时呆在同一个位置。
eg. 000000101000000 -> 0000100010000
最大值:选择从 \(0\) 端出去,从 \(L + 1\) 端出去的最远距离。
最小值:选择从 \(0\) 端出去,从 \(L + 1\) 端出去的最小距离。
(总时间取所有士兵出桥时间的最大值)