HDU/1009 2015年2月7日 (六) 13:51云璟月（讨论 | 贡献）的版本 (差异) ←上一版本 | 最后版本 (差异) | 下一版本→ (差异)

摘要

题目链接	难度等级	完成状态	完成分数	最后编辑时间	失误原因（初次提交分数）
FatMouse' Trade	★☆☆☆☆	答案正确	100	2015-02-06 13:49:23	输入超时（0）

• 来自寒假练习：Only a signing tool ! J题
• 原题链接：http://acm.hdu.edu.cn/showproblem.php?pid=1009

题意

初始m金钱，给出n个交易，分别是用Ji金钱换取Fi商品，问最终能获得的最大商品数量（商品可无限分割），即部分背包问题。

题解

• 贪心，按性价比排序，从高到低尽量多拿即可。
• cin/cout会超时……

代码

1009.cpp代码已折叠 展开折叠内容

#include<cstdio> #include<iomanip> #include<algorithm> using namespace std; class trade{ public: double require,provide; friend bool operator <(const trade &a,const trade &b) { return a.provide/a.require>b.provide/b.require; } bool Trade(double &M,double &ans) { if(M>=require&&provide>require) { M-=require; ans+=provide; return 1; }else{ ans+=M/require*provide; M=0; return 0; } } } p[1000]; int main() { while(1) { int n; double m,a,b,ans=0; scanf("%lf%d",&m,&n); if(n<-.5&&m<-.5) return 0; for(int i=1;i<=n;++i) scanf("%lf%lf",&p[i].provide,&p[i].require); sort(p+1,p+n+1); for(int i=1;i<=n;++i) { if(!p[i].Trade(m,ans)) break; } printf("%.3lf\n",ans); } }