[GDKOI2024 普及组] 刷野 I

dog_emperor · 2024-01-21 13:06:56 · 题解

题目传送门

分析

一道贪心题，这个贪心策略我还是想了比较久的。

贪心策略

设 hp_i 为第 i 只怪物血量，m 为能量。

我们可以看到有三种攻击方式：

优先选择第二、三种方式：

首先我们可以注意到第三种攻击，就是让所有怪兽 hp-1 的方式。还有第二种让一个怪兽 hp-2 的攻击方式。

显然，如果我们的怪兽总量是大于 2 的，那么我们会使用第 3 种攻击方式，因为无论如何，此时第二种造成的伤害总量最多为 2，而第三种最少就是 3，所以得出贪心策略一的结论：

• 当 m >0 并且 n > 2 时，优先选择第三种。

然后就是当 n \le 2 时的情况。

这时，使用第三种最多造成总伤害为 2，而第二种最少造成的伤害就是 2，所以此时优先选择第二种，得出贪心策略二的结论：

• 当 m >0 并且 n \le 2 时，优先选择第二种。

接下来就是 m =0 的时候了，这时候第二种第三种都用不了，那就只能使用第一种了，得出贪心策略三的结论：

• 当 m = 0 时，直接使用第一种。

梳理

现在我们把贪心策略已经想好了，对他们进行一下整理：

• 优先判断 m，如果 m>0 进行策略一二；

  继续判断，如果 n > 2 进行策略一，否则进行策略二。

• 否则 m = 0 进行策略三。

证明

这样的贪心方式为什么是对的呢？

因为对于每一个策略，我们都是选择了伤害越高的那种选择，并且最后的目标是干掉所有怪兽，我们对于每次攻击只在乎攻击的总量最高，而不是对于个体。

贪心策略伪代码：

if (还有能量) {
    if (怪兽总量 > 2) 
        进行第三种攻击;
    else
        进行第二种攻击;
} else {
    进行第一种攻击;
}

后话

有点像NOIP普及组守望者的逃离这道题，大家讲这两题一同食用更佳。