月饼是中国人在中秋佳节时吃的一种传统食品，不同地区有许多不同风味的月饼。现给定所有种类月饼的库存量、总售价、以及市场的最大需求量，请你计算可以获得的最大收益是多少。

注意：销售时允许取出一部分库存。样例给出的情形是这样的：假如我们有 3 种月饼，其库存量分别为 18、15、10 万吨，总售价分别为 75、72、45 亿元。如果市场的最大需求量只有 20 万吨，那么我们最大收益策略应该是卖出全部 15 万吨第 2 种月饼、以及 5 万吨第 3 种月饼，获得 72 + 45/2 = 94.5（亿元）。

输入格式：

每个输入包含一个测试用例。每个测试用例先给出一个不超过 1000 的正整数 N 表示月饼的种类数、以及不超过 500（以万吨为单位）的正整数 D 表示市场最大需求量。随后一行给出 N 个正数表示每种月饼的库存量（以万吨为单位）；最后一行给出 N 个正数表示每种月饼的总售价（以亿元为单位）。数字间以空格分隔。

输出格式：

对每组测试用例，在一行中输出最大收益，以亿元为单位并精确到小数点后 2 位。

输入样例：

3 20
18 15 10
75 72 45

输出样例：

94.50

编程语言：Python

解题思想：

1.贪心算法的思想，根据月饼的单价进行降序排序

2.对排序好的月饼列表进行逐个判断

3.注意输入时不能用int，需要用float

4.使用lambda函数、%.2f等用法

labmda函数：https://www.cnblogs.com/lovewhale1997/p/11424429.html

%.2f %x的用法：https://blog.csdn.net/imredboy/article/details/99189030

时间复杂度：O(N)

代码如下：

NOM, Requirement = map(int, input().split())  # 输入月饼种类数、总需求量(万吨)
Stock = list(map(float, input().split()))  # 各个月饼的库存(万吨)
Price = list(map(float, input().split()))  # 各个月饼的总售价(亿)
MoonCake = [[0, 0, 0] for i in range(NOM)]  # 创建月饼列表，存放各个月饼的总库存、总售价、售价/库存的比值
SaleCount = 0  # 最终卖出的总价
 
for i in range(NOM):
    MoonCake[i] = [Stock[i], Price[i], Price[i] / Stock[i]]
 
MoonCake.sort(key=lambda x: x[2], reverse=True)  # 使用labmda函数作为降序排序参数
# 在sort方法的key中使用labmda x:x[2]等同于使用MoonCake列表的第二个元素进行排序
 
i = 0
while Requirement > 0 and i < NOM:  # 仍有需求且月饼仍有库存
    if Requirement > MoonCake[i][0]:  # 当前需求>当前月饼总库存
        Requirement -= MoonCake[i][0]
        SaleCount += MoonCake[i][1]
        i += 1
    elif Requirement <= MoonCake[i][0]:  # 当前需求<=当前月饼总库存
        SaleCount += Requirement * MoonCake[i][2]
        Requirement = 0
 
print('%.2f' % SaleCount)

< >

评论板

共有 19 条评论

fruinly

Coenzyme Q CoQ 10 where to buy cialis online

2023-02-26 23:40 回复
engarma

Colton AFKcgFxYbg 6 27 2022 buy priligy 30mg

2023-04-25 16:44 回复
original louis vuittons outlet

I just wanted to thank you for the fast service. quite possibly they look great. I received them a day earlier than expected. like I will definitely continue to buy from this site. in any event I will recommend this site to my friends. Thanks!
original louis vuittons outlet https://www.cheapreallouisvuitton.com/

2023-04-30 16:41 回复
authentic louis vuitton outlet

I just wanted to thank you for the fast service. or possibly a they look great. I received them a day earlier than expected. love the I will definitely continue to buy from this site. in any event I will recommend this site to my friends. Thanks!
authentic louis vuitton outlet https://www.louisvuittonsoutletstore.com/

2023-04-30 19:47 回复
authentic cheap jordans

I just wanted to thank you for the fast service. aka they look great. I received them a day earlier than expected. choose to I will definitely continue to buy from this site. no matter what I will recommend this site to my friends. Thanks!
authentic cheap jordans https://www.realcheapretrojordanshoes.com/

2023-05-01 05:57 回复
cheap louis vuitton handbags

I just wanted to thank you for the fast service. along with they look great. I received them a day earlier than expected. particularly I will definitely continue to buy from this site. in any event I will recommend this site to my friends. Thanks!
cheap louis vuitton handbags https://www.bestlouisvuittonoutlet.com/

2023-05-01 08:53 回复
cheap jordans for sale

Read reviews and was a little hesitant since I had already inputted my order. or even a but thank god, I had no issues. the same as received item in a timely matter, they are in new condition. regardless so happy I made the purchase. Will be definitely be purchasing again.
cheap jordans for sale https://www.cheapsneakeronline.com/

2023-05-16 01:59 回复
louis vuitton outlet sale online

Read reviews and was a little hesitant since I had already inputted my order. or it may be but thank god, I had no issues. which includes received item in a timely matter, they are in new condition. in either case so happy I made the purchase. Will be definitely be purchasing again.
louis vuitton outlet sale online https://www.louisvuittonsoutletonline.com/

2023-05-16 17:04 回复
cheap jordans online

Read reviews and was a little hesitant since I had already inputted my order. possibly but thank god, I had no issues. the same as received item in a timely matter, they are in new condition. an invaluable so happy I made the purchase. Will be definitely be purchasing again.
cheap jordans online https://www.realjordansshoes.com/

2023-05-17 04:04 回复
Preliaf

Anemia, thyroid dysfunction, symptoms of obstructive sleep apnea, and depression are frequently part of the evaluation revatio vs viagra 5 5 mg L for 5 hours, daily for 7 days

2023-05-28 14:36 回复
Preliaf

415 ATORVASTATINA OPHALAC Atorvastatina 10 mg Caja x 10 tabs levitra prix en bretagne But we are still very worried fo course wont find out till 20 week scan if bump caught it too a long wait im, 10 weeks on wed

2023-06-09 10:43 回复
used gucci bags ebay

As the evergreen tree of Gucci, the Bacchus bag is also very popular. Today, I will show you the authenticity and fake identification points of Gucci~

2023-06-10 19:26 回复
Retro Air Jordan Shoes

Cheap Jordans 5 (V) Retro Fire Red Women

2023-06-10 19:57 回复
gucci shoulder handbags

Jo Ellison is one of the many fans of this unique bag. When the bag itself is complicated enough, our clothing must be very simple and clean. Alison is very unique with a gray suit and dark brown double-sided woolen coat for layering. The combination of neutral color and earth color is very harmonious, and the color is just in line with the composition of the bag, which is very carefully matched. ▼

2023-06-13 18:27 回复
cheap air jordans

In terms of color matching, it combines brilliant red, white, and dark gray, and the overall visual effect is very eye-catching.

2023-06-13 19:40 回复
vOekbmL

levitra 5 mg precio Since its approval in 1977, tamoxifen has been used to treat millions of women and men diagnosed with hormone receptor positive breast cancer

2023-07-09 07:32 回复

PAT乙级:1020 月饼