FatMouse准备了M磅的猫粮,准备与守卫仓库的猫交易,仓库里有他最喜欢的食物JavaBean。仓库有N个房间。第i个房间包含J[i]磅的JavaBeans,需要F[i]磅的猫粮。FatMouse不必交易房间里所有的JavaBeans,相反,如果他支付F[i]磅的猫粮,他可能会得到J[i]磅的JavaBeans。这里 a 是一个实数。现在他把作业交给你:告诉他他能获得的最大数量的JavaBeans
时间: 2023-05-28 09:06:52 浏览: 63
思路:贪心算法
首先计算每个房间的单位猫粮价值,即 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的数量,他把这个问题交给了你。