https://www.luogu.com.cn/problem/P1084
这道题难在贪心的思路,实现比较简单可以直接看代码。
首先二分。现在转化为判定问题。可以用倍增求出每个军队最上面能到哪。
结论1:
- 我们一定不会把在除了根节点以外的军队往下移动。否则肯定不优。
所以我们把能走到根节点的先存在一起最后处理,把不能到根节点的军队往上走到最高的位置然后固定。
现在我们可以拿到还需要我们去覆盖的根节点的子儿子的边权,和我们到根节点还能剩下的时间。
如果我们把这两个序列分别从大到小排序,然后
标签:NOIP2012,疫情,题解,军队,节点,我们 From: https://www.cnblogs.com/CloudWings/p/18363627