资讯详情

模型一：最优化

排序/优先队列

模型二：构造

例题1

此题分类讨论

• 对于打完还是赚的的关卡，按照 d 从小到大排序。
• 否则按照 r 从大到小排序（反正所有的d都得挨，不如先把大的r吃了）
  • 如果允许关卡内的时候血量可以为负，则按照 d，r 差值排序

可以利用交换思想证明（会掉血的关卡先打 r 大的更容易满足后面关卡 d 的条件）