HDU1009 FatMouse' Trade

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

<!--<br /> <br /> Code highlighting produced by Actipro CodeHighlighter (freeware)<br /> http://www.CodeHighlighter.com/<br /> <br /> -->#include<iostream>
#include<vector>
#include<algorithm>
#include<iomanip>
usingnamespacestd;
classHouse
{
private:
intnBean;
intnFood;
doubleratio;
public:
House(intnB,intnF):nBean(nB),nFood(nF)
{
ratio=static_cast<double>(nBean)/static_cast<double>(nFood);
}
intgetBeanNum()const
{
returnnBean;
}
intgetFoodNum()const
{
returnnFood;
}
doublegetRatio()const
{
returnratio;
}
booloperator<(constHouse&rhs)const
{
returnratio>rhs.ratio;
}
};


intmain()
{
intm,n,i,nB,nF;
doubletotal;
while(cin>>m>>n&&!(m==-1&&n==-1))
{
total=0.0f;
vector<House>vHouse;
for(i=0;i<n;++i)
{
cin>>nB>>nF;
Housetmp(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;
}
return0;
}