HDU1009 FatMouse' Trade

題目位址：http://acm.hdu.edu.cn/showproblem.php?pid=1009

#include <iostream>

#include <vector>

#include<algorithm>

#include <iomanip>

using namespace std;

class House

{

private:

    int nBean;

    int nFood;

    double ratio;

public:

    House(int nB,int nF):nBean(nB),nFood(nF)

    {

        ratio = static_cast<double>(nBean)/static_cast<double>(nFood);

    }

    int getBeanNum()const

        return nBean;

    int getFoodNum()const

        return nFood;

    double getRatio()const

        return ratio;

    bool operator < (const House& rhs)const 

         return ratio > rhs.ratio;

};

int main()

    int m,n,i,nB,nF;

    double total;

    while(cin>>m>>n&&!(m==-1&&n==-1))

        total = 0.0f;

        vector<House> vHouse;

        for(i=0;i<n;++i)

        {

            cin>>nB>>nF;

            House tmp(nB,nF);

            vHouse.push_back(tmp);

        }

        sort(vHouse.begin(),vHouse.end());

          //貪心算法

        for(i=0;i<vHouse.size()&&m>0;++i)

            if(m>vHouse[i].getFoodNum())

            {

                m -= vHouse[i].getFoodNum();

                total += vHouse[i].getBeanNum();

            }

            else

                total += m*vHouse[i].getRatio();

                m = 0;

                break;

        cout.setf(ios::fixed);

        cout.precision(3);

        cout<<total<<endl;

    return 0;

}

本文轉自Phinecos(洞庭散人)部落格園部落格，原文連結：http://www.cnblogs.com/phinecos/archive/2007/12/24/1012219.html，如需轉載請自行聯系原作者