Luogu P1007 – 独木桥

Luogu P1007 – 独木桥

  • 算法:贪心

思路如下:

  • 可以把士兵相遇后原路返回这个条件视作擦肩而过。可以想象的是,如果零时刻在p处有一名向右走的士兵,那么在第二个时刻必然有一名士兵在p+2位置向右走(假设p+2位置还没有离开独木桥),而我们并不关心这个士兵是不是零时刻时的那个士兵。
  • 每个士兵有两个选择:向左走和向右走,可以用贪心思想推理得出:最短疏散时间是所有士兵从离自己最近的一端下桥,即从所有士兵所用的较短时间中找到最大值;最长疏散时间是所有士兵从离自己最远的一端下桥,即从所有士兵所用的较长时间中找到最大值。(最后一个士兵下桥需要的时间才是所需的总共疏散时间)