NOIP2012BLOCKADE贪心思想证明

这道题的做法是二分时间并检验这个时间是否可行。检验的方法要用到贪心思想。

  1. 对于不能到根结点的军队应该尽量向根结点走。
  2. 如果军队A能走到根结点但到根结点后剩余的时间不够返回根结点的儿子B,应该让军队A守B。NOIP2012BLOCKADE贪心思想证明-LMLPHP
  3. 否则把军队A加入优先队列,用剩余时间小的军队匹配到根结点距离小的儿子。

证明:

  1. 一个军队可控制自己和以自己为根的子树。越向上走控制的结点越多。
  2. 把这个军队记作A,如果不这样,我们必须要用另一个到达根结点的军队,记作C,因为A剩余时间小于到B的时间,如果用C,则C剩余的时间大于到B的时间,这样交换以后在优先队列里的军队的剩余时间变小,不如不换更优。
  3. 假设军队A剩余的时间比军队B的多,则A能到的结点包扩所有B能到的结点,所以可能存在一些结点A能到但B不能到,所以一个结点B能到我们就不用A。
05-01 02:10