题目解析

我怀疑这个题目是 noip 国王的游戏的 原题

这也是一道非常经典的贪心算法题目，通常被称为**“比率调度问题” (Ratio Scheduling)** 或者 “史密斯规则” (Smith’s Rule)。

你会惊喜地发现，解这道题的核心思路，和你刚刚学到的**“微扰法/交换论证法”**（上一题小跳蛙的解法）是一模一样的！

1. 核心分析：谁是那个“猪队友”？

我们面临的问题是：有 $N$ 个敌人，每个人都有两个属性：

• 攻击力 ($DPS$)：他活着的时候每回合打你多疼。
• 血量 ($HP$)：你需要花多少回合才能弄死他。

直觉思考：

• 如果一个敌人攻击力超高（一刀999），但血量只有1点（一碰就死），你肯定想先杀他。因为只要花1回合，就能让你的每回合承伤大幅下降。
• 如果一个敌人攻击力很低（只挠痒痒），但血量超厚（肉盾），你肯定想最后杀他。因为杀他太费时间，期间会被其他人集火。

结论：我们需要根据某种“性价比”来排序。

2. 推导贪心策略（使用交换论证法）

考虑最简单的情况,只有两个人

假设现在只剩下两个敌人 A 和 B。

• 敌人 A：$DPS_A, HP_A$
• 敌人 B：$DPS_B, HP_B$

我们来比较两种击杀顺序的代价。注意：在你攻击当前目标时，两个人都还活着，都在输出伤害。

方案 1：先杀 A，再杀 B

1. 阶段 1（打 A）：耗时 $HP_A$。
   • 这段时间内，A 和 B 都在打你。
   • 每回合承伤：$DPS_A + DPS_B$。
   • 阶段总伤：$(DPS_A + DPS_B) \times HP_A$。
2. 阶段 2（打 B）：耗时 $HP_B$。
   • 此时 A 死了，只有 B 在打你。
   • 每回合承伤：$DPS_B$。
   • 阶段总伤：$DPS_B \times HP_B$。

方案 1 总伤害：

方案 2：先杀 B，再杀 A

逻辑同上，只是顺序换了：

方案 2 总伤害：

比较与做差

这时候，我们用方案 1 减去 方案 2，看看什么时候方案 1 更优（结果小于 0）：

如果你希望 先杀 A 更划算（即 $Cost_{AB} < Cost_{BA}$），那么必须满足：

为了方便理解，我们可以把两边的变量移项（除以 $HP_A \times HP_B$）：

最终策略：

你应该优先击杀 DPS 与 HP 之比（$\frac{DPS}{HP}$）最大 的敌人。

也就是：单位时间内能移除最多伤害的敌人优先解决。

推广到全体

现在我们应该如何简单的思考 $N > 2$ 的情况呢?

这个问题问到了贪心算法最核心的命门：如何证明“局部最优”一定能导致“全局最优”？

从 $N=2$ 推广到 $N$ 个人，最简单、最简洁的思路就是利用你一定熟悉的算法——冒泡排序 (Bubble Sort) 的逻辑。

这个证明思路叫：“邻项交换法” (Adjacent Swap Argument)。

核心逻辑：任何排列都可以通过“交换相邻元素”变成有序序列

假设你有一个包含 $N$ 个敌人的击杀顺序，而且这个顺序不是按照我们推导出的“性价比 ($DPS/HP$)”从大到小排列的。

1. 必然存在“逆序对”

如果序列不是完全有序的，那么在队伍里一定存在两个相邻的敌人（设为 $X$ 和 $Y$），其中排在前面的 $X$ 性价比反而比后面的 $Y$ 低。

即：位置上 $X$ 在 $Y$ 前，但数值上 $\frac{DPS_X}{HP_X} < \frac{DPS_Y}{HP_Y}$。

2. 交换“逆序对”会让结果变得更好

根据我们在 $N=2$ 时证明的结论：

对于这两个相邻的人，如果我们交换他们的位置（把性价比高的 $Y$ 放到 $X$ 前面），总伤害一定会减少。

3. 关键点：交换不影响其他人

这步最重要。你可能会担心：交换 $X$ 和 $Y$，会不会影响排在他们前面的 $A$ 或者排在后面的 $Z$ 呢？

• 对前面的人 ($A$)：$A$ 早就死了，$X$ 和 $Y$ 谁先死跟 $A$ 没关系。无影响。
• 对后面的人 ($Z$)：$Z$ 需要等 $X$ 和 $Y$ 都死完才能轮到他。无论 $X$ 先死还是 $Y$ 先死，这两人消耗的总时间都是 $HP_X + HP_Y$。所以 $Z$ 开始被打的时间点是不变的。无影响。

结论：交换相邻的 $X$ 和 $Y$，只会改变它们俩产生的伤害，而不会改变队伍里其他任何人的伤害贡献。由于 $N=2$ 的证明告诉我们要把性价比高的放前面，所以这次交换绝对是赚的。

4. 像冒泡排序一样不断变好

• 只要序列里还有“逆序对”（前面的比后面的弱），我们就交换它们。
• 每交换一次，总伤害就减少一点。
• 像冒泡排序一样，经过有限次交换后，序列必定变成严格按 $DPS/HP$ 从大到小排列。
• 因为每一步都在变好（或不变差），所以这个最终的“有序状态”，一定是所有可能排列中伤害最小的。

总结 (一句话思路)

如果最优解不是有序的，那我就一定能找到相邻的两个“反例”，把它俩换一下，结果会更优。既然一直换一直优，那最后的有序状态就是最最优。

这就是从 $2$ 推广到 $N$ 的标准逻辑！

4. 代码实现细节

虽然 $N$ 很小（只有20），我们可以用 $O(N^2)$ 甚至全排列解决，但既然推导出了贪心策略，$O(N \log N)$ 的排序显然是最优雅的。

注意点：

• 在代码中比较大小时，尽量使用乘法形式 $DPS_A \times HP_B > DPS_B \times HP_A$，避免除法带来的精度问题（虽然这题数据小，除法也没事，但这是好习惯）。
• 计算总伤害时，随着敌人一个个死去，当前的每回合总伤害是会减少的。

5. 参考代码 (C++)

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

struct Hero {
    int dps;
    int hp;
};

// 比较函数：性价比（DPS/HP）高的排前面
// 转化为乘法形式：a.dps * b.hp > b.dps * a.hp
bool compareHeroes(const Hero &a, const Hero &b) {
    return a.dps * b.hp > b.dps * a.hp;
}

void solve() {
    int n;
    while (cin >> n) {
        vector<Hero> heroes(n);
        long long currentTotalDPS = 0; // 当前所有活着的敌人的总DPS

        for (int i = 0; i < n; i++) {
            cin >> heroes[i].dps >> heroes[i].hp;
            currentTotalDPS += heroes[i].dps;
        }

        // 核心步骤：排序
        sort(heroes.begin(), heroes.end(), compareHeroes);

        long long totalLoss = 0;

        // 模拟攻击过程
        for (int i = 0; i < n; i++) {
            // 1. 在消灭当前敌人(heroes[i])的过程中，我们要承受 currentTotalDPS 的伤害
            //    持续时间是 heroes[i].hp 回合
            totalLoss += currentTotalDPS * heroes[i].hp;

            // 2. 当前敌人死了，他的 DPS 从总输出中移除
            currentTotalDPS -= heroes[i].dps;
        }

        cout << totalLoss << endl;
    }
}

int main() {
    solve();
    return 0;
}

5. 复杂度分析

• 时间复杂度：主要消耗在排序上，为 $O(N \log N)$。对于 $N=20$ 来说，这简直是瞬时的。
• 空间复杂度：$O(N)$ 用来存储敌人信息。

6. 总结

这道题再次印证了**“交换论证法”**的强大。

• 在题目《跳跳》[[problem: luogu,P4995]] 中，我们通过交换路径证明了要最大化差值（大配小）。
• 在这一题 DOTA 中，我们通过交换击杀顺序证明了要最大化比率（先杀高攻低血）。

这两道题结合起来，你就掌握了贪心算法中最重要的一类题型——**排序贪心（Scheduling Problems）**的精髓。