密码
不难发现取对就做完了。
挑战
基本上一样的原题：Complete the Projects (hard version)
首先，对于 $a_i \le b_i$ 的，我们选择了也不会有什么损失，直接按照 $a_i$ 排序从小到大拿就好了。
对于 $a_i > b_i$ 怎么处理呢？可以猜几个贪心结论但是会发现都是错的。我们考虑，如果已经知道了要选择的物品是哪些，设为 $(A_i,t_i)$ ，其中 $t_i = a_i - b_i$ ，也就是在选择这个物品后所损失的血量。我们能否找到一种排列顺序，使得所需要的初始血量尽量少。倒着做这个过程，本质上就是有一个变量 $s$ 初始为 $0$ ，依次经过每个物品，经过一个物品时会给 $s$ 加上 $t_i$ 后与 $A_i$ 取最大值。这么操作一遍后 $s$ 的值尽量小。
然后考虑对于一对 $(i,j)$ 在满足什么条件的时候会把 $i$ 放到 $j$ 前面，也就是如果先选 $i$ 再选择 $j$ 一定比先选择 $j$ 再选择 $i$ 的情况优。考虑写出在进入时为 $s$ 时两种情况分别对应的血量：
如果第一种比第二种优，即意味着：
这个不等式有几种情况，
- 化简出来是 $A_j < A_i$， 这不可能，因为这意味着 $A_j > A_i > A_j + t_i , t_i > 0$
- $A_j > A_i + t_j$ ，也就是说不等式等价于 $A_j < A_j + t_i$ ，这个不等式必然成立。
- $A_i > A_j + t_i$ ，也就是说不等式等价于 $A_i + t_j < A_i$ ，这个不等式必然不成立。
- $A_i + t_j > A_j,A_j + t_i > A_i$ ，不等式就等价于 $A_i + t_j < A_j + t_i$ ，不难发现如果第二个条件成立，这个条件就一定成立，第三个条件成立，这个条件就一定不成立。所以说，对于 $A_i - t_i < A_j - t_j$ 的情况，我们把 $i$ 放在前面一定不劣于把 $j$ 放前面。对于这个东西不成立的情况，我们把 $i$ 放前面一定不优于 $j$ 放前面。
现在我们说明了对于确定了选择的物品后，直接拿 $A_i - t_i$ 降序排序即可获得一个最优的操作序列。
但是在这个题中，我们是选择尽量多的物品使得初始血量为某个值的时候可以操作到结尾。
我们可以倒着 $dp$ 算出当前初始血量为某个值的时候的答案。但是这样算复杂度是背包的复杂度 $O(nw)$ ，由于 $w$ 在进行了第一种操作后可能达到 $10^6$ 可能无法通过。
但是设 $dp[i]$ 表示如果要在后面选择 $i$ 个物品，最少需要的初始血量，我们就可以优化到 $O(n^2)$ 。
硬币
一个经典的套路：这道题这种形式的物品可以拆成 $a_i$ 容量为 $1$ ，$a_i+b_i$ 容量为 $2$ 。
然后可撤销贪心即可，按照性价比排序，然后选择前面的一段。如果最后一次选择的是 $2$ ，我们撤销一定是删最后一个位置，然后加入一个后面的 $1$ 或者是删除之前的一个 $1$ 。比一下哪个更优秀即可。
精灵
不难发现本质上就是 福慧双修 。
卡常：不难发现在 dijk 跑到第一个结尾点的时候，就没必要往后跑了直接返回即可。
即使用 spfa 也跑不过。