原题传送门:http://acm.hdu.edu.cn/showproblem.php?pid=1009
FatMouse' Trade
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 42086 Accepted Submission(s): 14004
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.
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
分析:这是一个简单的贪心算法,部分背包问题,用结构体数组,以J/F比值升序排序即可。然后遍历数组的时候判断每个房间能不能全拿,如果能就left-F,total+=J,不能就按照比例来取,在不能的时候Mouse用尽M的时候,这时候break就ok了,注意百分比计算的时候的强制转换。
//部分背包问题 贪心算法 HDU1009 #include<cstdio> #include<algorithm> using namespace std; const int MAXN = 1100; struct Value{ int J; int F; double j_f; }; bool cmp(Value a,Value b){ return a.j_f>b.j_f; } int N,M,j,f,leftM; double total; Value p[MAXN]; int main(){ while(scanf("%d%d",&M,&N) ==2){ if(M == -1&&N ==-1)break; leftM = M; total = 0; for(int i=0;i<N;i++){ scanf("%d%d",&j,&f); p[i].J = j; p[i].F = f; p[i].j_f = ((double)j)/f; } sort(p,p+N,cmp); for(int i=0;i<N;i++){ if(p[i].F<=leftM){ leftM = leftM - p[i].F; total += p[i].J; }else{ total += (((double)leftM)/p[i].F * p[i].J); break; } } printf("%.3f\n",total); } return 0; }
相关推荐
HDU的1250,主要是利用高精度加法,但是代码有点繁琐,效率不是很高
HDU1059的代码
杭电ACMhdu1163
hdu1001解题报告
hdu 1574 passed sorce
HDU的一题........HDU DP动态规
hdu acm 教案 搜索入门 hdu acm 教案 搜索入门
hdu2101AC代码
搜索 dfs 解题代码 hdu1241
hdu acm 教案 动态规划(1) hdu acm 教案 动态规划(1)
ACM HDU题目分类,我自己总结的大概只有十来个吧
hdu 5007 Post Robot 字符串枚举。 暴力一下就可以了。
HDU最全ac代码
hdu 1166线段树代码
hdu动态规划算法集锦
hdu-acm源代码(上百题)hdu-acm源代码、hdu-acm源代码hdu-acm源代码
hdu题目分类
自己做的HDU ACM已经AC的题目
ACM/ICPC 2010年多校联合第十场第九题的解题报告及代码,AC代码有三个,最好的是src
HDU图论题目分类