FatMouse的交易

题目描述

FatMouse准备了M磅的猫食，并准备与守卫着他最喜欢的食物JavaBean的仓库的猫进行贸易。仓库有N个房间。第i个房间包含J [i]磅JavaBeans，并且需要F [i]磅猫食。FatMouse不必在房间内交易所有JavaBeans，相反，如果他支付F [i] * a％的猫食，他可能会得到J [i] * a％的JavaBeans。这是一个实数。现在，他正在将这项作业分配给您：告诉他可以获取的最大JavaBeans数量。

输入

输入包含多个测试用例。每个测试用例都从包含两个非负整数M和N的行开始。然后是N行，每行分别包含两个非负整数J [i]和F [i]。最后一个测试用例后跟两个-1。所有整数均不大于1000。

输出

对于每个测试用例，请在一行中打印精确到3个小数位的实数，这是FatMouse可以获得的JavaBeans的最大数量。

样例输入

5 3
7 2
4 3
5 2
20 3
25 18
24 15
15 10
-1 -1

样例输出

13.333
31.500

题解

这是一个贪心题，就是把房间按照单位猫粮所能收益的最大javabean排序，从前往后遍历，有剩余猫粮就兑换

#include<iostream>
#include<algorithm>
using namespace std;
struct house
{
 double javabean; 
 double catfood;//猫粮 
 double ave;//记录平均收益 
}h[1010]; 
bool cmp(house h1,house h2)
{
 return h1.ave>h2.ave;
}
int main()
{
 int i,j,n;
 double sum,m;//记录获得的javabean 
 while(cin>>m>>n)//m是总猫粮,n是房间数 
 {
  if(m==-1&&n==-1) break;
  sum=0;
  for(i=1;i<=n;i++)
  {
   cin>>h[i].javabean>>h[i].catfood;
   h[i].ave=h[i].javabean/h[i].catfood;
  }
  sort(h+1,h+1+n,cmp);//按照单位收益最大排序
  for(i=1;i<=n;i++)
  {
   //总猫粮大于该房间所需的最大猫粮，说明可以继续访问下一个房间
   if(h[i].catfood<m) 
   {
    sum+=h[i].javabean;
    m-=h[i].catfood; 
   }
   //总猫粮小于该房间所需的最大猫粮，循环终止 
   else
   {
    sum+=m*h[i].ave;
    break;
   }
  } 
  printf("%.3f\n",sum);
 }
 return 0;
}