【1009】FatMouse‘ Trade

【1009】FatMouse’ Trade

题目地址
贪心

FatMouse准备了M磅猫粮，准备和守卫仓库的猫咪交易，仓库里有他最喜欢的食物JavaBean。
仓库有N个房间。第i个房间里有J[i]磅的JavaBeans，需要F[i]磅的猫粮。FatMouse不需要交易房间里所有的JavaBeans，相反，如果他支付F[i]* a%磅的猫粮，他可以得到J[i]* a%磅的JavaBeans。这里a是一个实数。现在他把这个作业交给你：告诉他可以获得的最大数量的JavaBeans。

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

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

通过www.DeepL.com/Translator（免费版）翻译

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

#include 
using namespace std;
struct trade
{double a;double b;double c;
}fj[1001];
int compare(trade x,trade y)
{return x.c>y.c;//运用结构体变量存储，
}
int main()
{int m,n,i;double j,f,sum;while (scanf("%d%d",&m,&n)&&(m!=-1&&n!=-1)){sum=0;//可获得的javabeansfor (i=0;i<n;i++){scanf("%lf%lf",&j,&f);fj[i].a=j;//javabeansfj[i].b=f;//猫粮 fj[i].c=j/f;//比率 }sort(fj,fj+n,compare);//用结构体中的c变量的大小进行排序，从大到小 for (int k=0;k<n;k++){if (m-fj[k].b>0.001){sum+=fj[k].a;m-=fj[k].b;}//当m大于整体的b时else{sum+=m*fj[k].a/fj[k].b;break;}//当m不能整体换时！}printf("%.3lf\n",sum);}
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！