信息
- ID
- 48
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 3
- 标签
- 递交数
- 1
- 已通过
- 1
- 上传者
对于前20分,暴力枚举使用药水的时机即可。
考虑使用反悔贪心,当遇到新的怪物时,尽可能使用药水,如果没有药水可以用,则检查之前用过药水的怪物造成伤害的最小值,若比当前怪物造成的伤害少则改为对当前怪物使用药水,血量减去被反悔的怪物的攻击力。暴力枚举时间复杂度为O(n2)。
使用优先队列维护使用过药水的怪物的攻击力可以将时间复杂度压缩至O(nlog2n)。
也可以先二分答案,假设可以击败前 c 个怪物,那么从贪心的角度,一定会把伤害最高的 k 个怪物免疫,如果提前离散化,每次二分答案的时候桶排,时间复杂度为 O(nlog2n)