题目地址：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，如需转载请自行联系原作者
