这也属于一个贪心题。关键是排序的依据。
这题排序的依据是敌人的伤害/血量（DPS/HP），不难证明，当这个比值相同时，不论先解决谁效果是相同的。思路大部分在注释里。
题目大意：
假设你的血量无限，但是你的伤害每次只有1点。现在你有N个敌人，给出他们的血量和伤害，要你在损失血量最少的情况下，解决所有敌人。
样例输入：（第一行整数N指有N个敌人，后面N行输入对应敌人的血量和伤害）
1
10 2
2
100 1
1 100
样例输出：
20
201
#include<iostream>
#include<algorithm>
using namespace std;
struct DOTA//保存敌军的血量和伤害
{
double HP,DPS;
}; bool comp(DOTA a,DOTA b)//按照（伤害）/（血量）进行降序排序。即优先解决伤害高、血量少的
{
return a.DPS/a.HP>b.DPS/b.HP;
} int main()
{
int n,i;
DOTA hero[];
while(cin>>n)
{
double lose=,harm=;
for(i=;i<n;i++)
{
cin>>hero[i].HP>>hero[i].DPS;
harm+=hero[i].DPS;//第一次受到的总伤害
}
sort(hero,hero+n,comp);
for(i=;i<n;i++)
{
lose+=harm*hero[i].HP;//把每次丢失的血量进行累加
harm-=hero[i].DPS;//解决掉一个后对应的总伤害要减掉
}
cout<<lose<<endl;
}
return ;
}