比較簡單的貪心。
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
using namespace std;
int n;
struct Hero {
int dps, hp;
}hero[22];
bool cmp(Hero a, Hero b)
{
return ((a.dps + b.dps) * a.hp + b.dps * b.hp) < ((b.dps + a.dps) * b.hp + a.dps * a.hp);
}
int main()
{
while (scanf("%d", &n) != EOF) {
int totDps = 0;
__int64 hpLoss = 0;
for (int i = 0; i < n; ++i) {
scanf("%d %d", &hero[i].dps, &hero[i].hp);
totDps += hero[i].dps;
}
sort(hero, hero + n, cmp);
for (int i = 0; i < n; ++i) {
hpLoss += totDps * hero[i].hp;
totDps -= hero[i].dps;
}
printf("%I64d\n", hpLoss);
}
return 0;
}