题目描述 当你与神一般的对手和猪一般的队友玩DotA时，你必须面对一个尴尬的局面:你的队友都被杀了，你必须打1vN。 游戏中的英雄有两个关键属性，生命值(HP)和每次射击伤害(DPS)。你的英雄几乎有无限的HP，但只有1点DPS。 为了简化问题，我们假设游戏是回合制的，但不是实时的。在每个回合中，你可以选择一个敌人英雄进行攻击，他的HP将减少1。同时，所有活着的敌人英雄都会攻击你，你的HP会以t的总和递减 输入 每个测试用例的第一行包含敌人英雄的数量N (1 <= N <= 20)。 接下来是N行，每一行包含两个整数DPSi和HPi，分别表示每个英雄的DPS和HP。(1 <= DPSi, HPi <= 1000) 输出 每次测试输出一行，表示最小的HP损耗。 样例输入 复制 2 100 1 1 100 样例输出 复制 201 来源/分类 贪心

解题思路 游戏为回合制，每回合可攻击一名敌方英雄，使其HP减1。 所有存活的敌方英雄每回合对我方造成总DPS点伤害。 目标：最小化我方承受的总伤害。 贪心策略 优先攻击DPS/HP比值高的敌人。 理由： - 敌方英雄存活越久，造成的总伤害越多。 - 应优先消灭单位时间内伤害输出效率高的敌人。 排序规则 按 `DPS/HP` 降序排序，若比值相同，则按DPS降序排序。 计算总伤害 设敌方英雄按排序后顺序为 `1, 2, ..., N`。 总伤害 = Σ(第i个英雄存活期间造成的伤害) 第i个英雄存活回合数 = 其HP值（因为每回合对其造成1点伤害）。 在击败前i-1个英雄期间，第i个英雄一直存活。 因此： 总伤害 = Σ( DPS[i] * (HP[1] + HP[2] + ... + HP[i]) ) 样例验证 输入： 2 100 1 1 100 排序： 英雄1: DPS=100, HP=1, 比值=100 英雄2: DPS=1, HP=100, 比值=0.01 按比值降序，顺序不变。 计算： 总伤害 = 100*1 + 1*(1+100) = 100 + 101 = 201 输出：201 ✅ 代码实现 ```cpp #include <iostream> #include <vector> #include <algorithm> using namespace std; struct Hero { int dps; int hp; }; bool cmp(const Hero &a, const Hero &b) { // 按 DPS/HP 降序排序，比值相同按 DPS 降序 // 为避免浮点数比较，使用交叉相乘 return a.dps * b.hp > b.dps * a.hp; } int main() { int n; while (cin >> n) { vector<Hero> heroes(n); for (int i = 0; i < n; i++) { cin >> heroes[i].dps >> heroes[i].hp; } // 贪心排序 sort(heroes.begin(), heroes.end(), cmp); long long totalDamage = 0; long long totalHP = 0; for (int i = 0; i < n; i++) { totalHP += heroes[i].hp; // 当前英雄存活期间的总HP累计 totalDamage += heroes[i].dps * totalHP; } cout << totalDamage << endl; } return 0; } ``` [2026-01-01 00:14:47 | AI问答 | 609点数解答]