这道题还是 好做的,也好理解,很明显的贪心,然而,最开始我的思路有问题,不能只看hp或者DPS,要综合考虑,所以相乘相除都可以,就是不能只看一个。
#include <stdio.h>
#include <algorithm>
using namespace std;
struct Node
{
int dps;
int hp;
}a[30];
int cmp(Node x,Node y)
{
return x.hp*y.dps<y.hp*x.dps;//按比率排,避免小数,所以讲式子进行转换
}
int main()
{
int t,i;
int sum,ans;
while(~scanf("%d",&t))
{
sum = ans = 0;
for(i = 0;i<t;i++)
{
scanf("%d%d",&a[i].dps,&a[i].hp);
sum+=a[i].dps;
}
sort(a,a+t,cmp);
for(i = 0;i<t;i++)
{
ans+=sum*a[i].hp;
sum-=a[i].dps;
}
printf("%d\n",ans);
}
return 0;
}
原文:http://www.cnblogs.com/yintoki/p/5696858.html