m,第 i 个咒语先扣 a_i,若此时 m-a_i<=0 则失败;若存活,再加 b_i,即 m ← m - a_i + b_i。贪心策略(经典“阈值+收益”排序):
魔法学院的某学员有一天早上准备起床的时候,突然发现有人在他的被子上施加了 n 道昏睡魔法,被子上每道魔法施加完毕后该学员都会减少 ai 点清醒值,而该学员每一次面对魔法都会进行抵抗,使自己的清醒值增加 bi (只有当被子施法完成后才增加),初始时该学员的清醒值为 m 。
而该学员作为魔法学院的学生也不是吃素的,他有一道魔法可以指定被子的施法顺序,但因为他有点紧张所以很难冷静思考,你能帮忙看看是否该学员可以挣脱被子的昏睡魔法吗?
如果被子的昏睡魔法以某种顺序施法时,若存在某一次施法后该学员的清醒值 ≤0 ,则认为该学员挣脱失败。