注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

Minary_Acdream

http://f10.moe/

 
 
 

日志

 
 

[hdu]1009 FatMouse' Trade  

2012-08-03 15:39:48|  分类: HDU |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
简单的背包问题,好像以前有看过这题但是没有做,现在去做就觉得...简单了。
果然好弱。。

题目:

FatMouse' Trade

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 24703    Accepted Submission(s): 7794


Problem Description
FatMouse prepared M pounds of cat food, ready to trade with the cats guarding the warehouse containing his favorite food, JavaBean.
The warehouse has N rooms. The i-th room contains J[i] pounds of JavaBeans and requires F[i] pounds of cat food. FatMouse does not have to trade for all the JavaBeans in the room, instead, he may get J[i]* a% pounds of JavaBeans if he pays F[i]* a% pounds of cat food. Here a is a real number. Now he is assigning this homework to you: tell him the maximum amount of JavaBeans he can obtain.
 

Input
The input consists of multiple test cases. Each test case begins with a line containing two non-negative integers M and N. Then N lines follow, each contains two non-negative integers J[i] and F[i] respectively. The last test case is followed by two -1's. All integers are not greater than 1000.
 

Output
For each test case, print in a single line a real number accurate up to 3 decimal places, which is the maximum amount of JavaBeans that FatMouse can obtain.
 

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

Sample Output
13.333 31.500
 

Author
CHEN, Yue
 

Source
 

Recommend
JGShining
 


代码:


#include<iostream>
#include<stdio.h>
#include<string>
#include<cmath>
#include<algorithm>
using namespace std;

struct JF
{
double J,F;
}J_F[1010];


bool cmp(JF a,JF b)
{
return a.J / a.F > b.J / b.F;
}

int main()
{
int M,N;
while(cin>>M>>N,!(M == -1 && N == -1))
{
double sum = 0;
for(int i = 0;i < N;i ++) scanf("%lf%lf",&J_F[i].J,&J_F[i].F);
sort(J_F,J_F + N,cmp);
double remain = M;
for(int i = 0;i < N;i ++)
{
if(remain>=J_F[i].F)
{
remain -= J_F[i].F;
sum += J_F[i].J;
}
else
{
sum += remain / J_F[i].F * J_F[i].J;
break;
}
}
printf("%.3lf\n",sum);
}
}


/*
M and N.
J[i] F[i]
The last test case is followed by two -1's.
All integers are not greater than 1000.
Sample Input
5 3
7 2
4 3
5 2
20 3
25 18
24 15
15 10
-1 -1


Sample Output
13.333
31.500*/



  评论这张
 
阅读(91)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018