/*
input:
53
72
43
52
output
13.333
5個(gè)貓食，3個(gè)房間，第1個(gè)房間2個(gè)貓食換7個(gè)JavaBean，第2個(gè)房間3個(gè)貓食換4個(gè)JavaBean，第3個(gè)房間2個(gè)貓食換5個(gè)JavaBean；
最大量的JavaBean是7+5+(1/3)*4=13.333。
簡(jiǎn)單的貪心策略:每次以最小量的貓食換最大量的JavaBean，即每次取(J[i]/F[i])最大的J[i]將使換得的JavaBean量最大。
*/
#include
<
algorithm
>
#include
<
iostream
>
#include
<
vector
>
using
namespace
std;
struct
JavaBeanCaCatFood
{
int
JavaBean,CatFood;
}
;
bool
cmp(JavaBeanCaCatFooda,JavaBeanCaCatFoodb)
{
return
(
double
)a.JavaBean
/
a.CatFood
>
(
double
)b.JavaBean
/
b.CatFood;
}
bool
run()
{
int
n,m;
cin
>>
m
>>
n;
if
(m
==-
1
&&
n
==-
1
)
return
false
;
vector
<
JavaBeanCaCatFood
>
JavaBeanCaCatFood(n);
int
i;
for
(i
=
0
;i
<
n;i
++
)cin
>>
JavaBeanCaCatFood[i].JavaBean
>>
JavaBeanCaCatFood[i].CatFood;
sort(JavaBeanCaCatFood.begin(),JavaBeanCaCatFood.end(),cmp);
double
s
=
0
,t
=
0
;
for
(i
=
0
;i
<
n;i
++
)
{
if
(m
>=
JavaBeanCaCatFood[i].CatFood)
//
i房間的能全換
{
m
-=
JavaBeanCaCatFood[i].CatFood;
t
+=
JavaBeanCaCatFood[i].JavaBean;
}
else
{
t
+=
JavaBeanCaCatFood[i].JavaBean
*
((
double
)m
/
JavaBeanCaCatFood[i].CatFood);
//
剩下不夠全換
break
;
}
}
printf(
"
%.3lf
"
,t);
return
true
;
}
int
main()
{
while
(run());
return
0
;
}
更多文章、技術(shù)交流、商務(wù)合作、聯(lián)系博主
微信掃碼或搜索：z360901061
微信掃一掃加我為好友
QQ號(hào)聯(lián)系： 360901061
您的支持是博主寫作最大的動(dòng)力，如果您喜歡我的文章，感覺我的文章對(duì)您有幫助，請(qǐng)用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧，狠狠點(diǎn)擊下面給點(diǎn)支持吧，站長(zhǎng)非常感激您！手機(jī)微信長(zhǎng)按不能支付解決辦法：請(qǐng)將微信支付二維碼保存到相冊(cè)，切換到微信，然后點(diǎn)擊微信右上角掃一掃功能，選擇支付二維碼完成支付。
【本文對(duì)您有幫助就好】元
