HDU 4310 Hero（貪心）

比較簡單的貪心。

#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;
}