题目地址:http://acm.hdu.edu.cn/showproblem.php?pid=1009
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 66570 Accepted Submission(s):
22635
#include<cstdio> #include<algorithm> using namespace std; struct Huan { double j,f; double c; }huan[3005]; bool cmp( Huan a, Huan b) { return a.c > b.c ; } int main() { double m; int n,t; while( scanf("%lf%d", &m, &n)!=EOF && ( m!=-1 || n!=-1 ) ) { int i, j, k; double sum=0; for( i=0; i<n; i++) { scanf("%lf%lf", &huan[i].j, &huan[i].f); huan[i].c = huan[i].j / huan[i].f; } sort(huan, huan+n, cmp);//按f从小到大排序 for( i=0; i<n; i++) { if( m >= huan[i].f )//全盘换了 { sum += huan[i].j; m -= huan[i].f; } else//大米的数量不足全盘换 { sum += m*huan[i].c ; break; } } printf("%.3lf\n",sum); } return 0; }
原文:http://www.cnblogs.com/123tang/p/5699561.html