关于贪心的题

题意理解：

dps、hp分别代表攻击力和血值。在回合制中，你与n个英雄战斗，己方hp无限，dps为1. 问击败所有英雄（hp=0），受到的最少dps和。

抽象出来就是，将敌方英雄排列起来，逐个击败，且受到的dps之和最小，典型的当前最佳问题，

分析

我先分析了三种情况，dps优先，hp优先，dps*hp优先，但是都不正确。 对此，我肯定要先解决总dps最大的，这里的dps最大应该是体现在整个序列上，即，若有两个英雄，后被解决的英雄的总dps是两个英雄的总hp乘其dps，我们要解决，一个英雄，当其放在后一个解决时，伤害更大。所以要先解决他。

所以之前的三种情况都不对，可以看出每个英雄的基本伤害是其dps和hp之积，我们要探究的是其放在后一位的情况下的伤害大小

思路：

使用结构体存每个英雄的dps和hp，再进行排序，排序的cmp是前者的dps与后者的hp之积，和前者二点hp与后者的dps之积进行比较，我们肯定解决更大的那个。再逐个累加，，hp也逐个累加。

#include<iostream>
#include<algorithm>
using namespace std;
typedef struct her {
	int dps;
	int hp;
}heros;
bool cmp(heros a, heros b) {
	return a.dps * b.hp > a.hp * b.dps;
}
int main() {
	int N;
	while (cin >> N) {
		heros hero[20];
		for (int i = 0; i < N; i++) {
			cin >> hero[i].dps >> hero[i].hp;
		}
		sort(hero, hero + N, cmp);
		int h=0,res=0;
		for (int i = 0; i < N; i++) {
			h += hero[i].hp;
			res += hero[i].dps * h;
		}
		cout << res << endl;
	}




	return 0;
}