1000ms

Difficulty: 6

算法与标签>贪心算法

会员专享

请先登录，开通会员或购买该题目所属题库，可解锁完整内容。

开通会员

会员专享

请先登录，登录后可使用今日免费解锁；开通会员，或购买该题目所属题库，可解锁完整内容。

开通会员

题解思路与方法

问题建模

给定 $n$ 只怪物，每只怪物有血量 $a_i$ ；有 $m$ 支箭，每支箭有伤害 $b_j$ 和花费 $c_j$ 。每支箭只能用一次，且一次只能击中一只怪物，要求击杀所有怪物的最小总花费，若无法全部击杀则输出 No。

算法选择：贪心 + 优先队列

贪心策略：优先处理血量最大的怪物，因为它对箭的伤害要求最高，若先打小怪物可能会浪费高伤害低花费的箭。

题目内容

现在有 $n$ 个怪物，每一个怪物有一定的血量，你手里有 $m$ 只箭，每一只箭都有一个伤害值，同时也有一个花费。

我们现在假设每一只箭只能用一次并且每一个怪物也只能射一次，想要把所有怪物都击杀问最少需要花费多少，若无法全部击杀，则输出 $No$ 。