FatMouse准备了M磅的猫粮，准备与守卫仓库的猫交易，仓库里有他最喜欢的食物JavaBean。仓库有N个房间。第i个房间包含J[i]磅的JavaBeans，需要F[i]磅的猫粮。FatMouse不必交易房间里所有的JavaBeans，相反，如果他支付F[i]磅的猫粮，他可能会得到J[i]磅的JavaBeans。这里 a 是一个实数。现在他把作业交给你：告诉他他能获得的最大数量的JavaBeans。 输入 输入由多个测试用例组成。每个测试用例都以包含两个非负整数 M 和 N 的行开头。然后是 N 行，每行分别包含两个非负整数 J[i] 和 F[i]。最后一个测试用例后跟两个 -1。所有整数都不大于 1000。 输出 对于每个测试用例，在一行中打印一个精确到小数点后 3 位的实数，这是 FatMouse 可以获得的最大 JavaBeans 数量。

思路：

这是一道贪心题目，需要对每个房间的单位价格（即每磅JavaBeans所需的猫粮）进行排序，然后从价格最低的房间开始交易，直到猫粮用完或者所有房间都交易完为止。

具体实现时，可以定义一个Price结构体，其中包含房间编号、单位价格和房间容量。然后将所有房间的Price结构体放入一个数组中，并按照单位价格从小到大排序。接着从头开始遍历数组，每次判断当前房间是否能全部买下，如果能，则花费全部猫粮买下；否则只买能够买下的部分，并更新剩余猫粮。最后统计买到的JavaBeans总量即可。

代码实现：

相关问题

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

思路：贪心算法

首先计算每个房间的单位猫粮价值，即 J[i] / F[i]，然后按照这个价值将房间从大到小排序。然后从价值最高的房间开始遍历，直到猫粮用完或者所有房间遍历完为止。每遍历一个房间，就将当前剩余的猫粮与该房间需要的猫粮进行比较，如果剩余猫粮大于等于该房间需要的猫粮，就可以全部交易，否则只能部分交易，交易的数量为剩余猫粮与该房间单位猫粮价值的乘积。最后得到的就是最大的JavaBeans数量。

时间复杂度：O(nlogn)，主要是排序的时间复杂度。

代码：

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.

这道题目的意思是，fatmouse准备了m磅猫粮，他想用这些猫粮与守卫着javabean仓库的猫们交换他最喜欢的javabean。仓库里有n个房间，第i个房间里有j[i]磅javabean，交换需要f[i]磅猫粮。fatmouse并不需要交换房间里所有的javabean，他可以支付f[i]*a%磅猫粮来获得j[i]*a%磅javabean。现在他想知道他最多能获得多少javabean的数量，他把这个问题交给了你。