DotA 1vN 难题：巧用贪心策略最小化 HP 损耗！

解题思路 游戏为回合制，每回合可攻击一名敌方英雄，使其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; } ``` ######[AI问答 | 609点数解答 | 2026-01-01 00:14:47]