hdu4310 - Hero - 简单的贪心

/*
@theme:hdu 4310
@writer:pprp
@declare:简单的贪心算法 将攻击力/血量最高的敌人先进攻下来就行了
@date:2017/8/26
*/
#include <bits/stdc++.h>

using namespace std;
class enemy
{
public:
    double dps;
    double hp;
} emy[1010];


struct cmp
{
    bool operator()(const enemy& a, const enemy&b)
    {
        return a.dps/a.hp > b.dps/b.hp;
    }
};

int main()
{
    int n;

    while(cin >> n && n >= 1 && n <= 20)
    {
        double ans = 0;
        double sum_dps = 0;
        for(int i = 0 ; i < n ; i++)
        {
            cin >> emy[i].dps >> emy[i].hp;
            sum_dps += emy[i].dps;
        }

        sort(emy, emy + n,cmp());

//        for(int i = 0 ; i < n ;i++)
//        {
//              cout << emy[i].dps << " " << emy[i].hp << endl;
//        }

        for(int i = 0 ; i < n ; i++)
        {
            if(i == 0)
            {
                ans += emy[0].hp * sum_dps;
            }
            else
            {
                sum_dps -= emy[i-1].dps;
                ans += emy[i].hp * sum_dps;
            }
        }

        cout << ans << endl;
    }
    return 0;
}