水果购买最小最大花费 - 算法题解

水果购买最小最大花费 - 算法题解

题目描述

春天到了，很多水果都出现在了柜台上。一个阳光明媚的日子，小男孩瓦列拉决定去购物。他列了一个清单，上面写着他要买的 m 种水果。如果瓦列拉想买一种水果超过一次，他就在清单上写上多次。

当他来到阿肖特的水果摊时，他发现卖家没有给商品贴价格标签，而是把所有的价格标签都放在了柜台上。之后，阿肖特会把每个价格标签贴到某种水果上，瓦列拉就可以算出他清单上所有水果的总价。但瓦列拉现在就想知道，在最‘幸运’（对他来说）的价格标签分配情况下，最小总价是多少？（在最‘不幸’（对他来说）的价格标签分配情况下，最大总价是多少？

输入格式

输入的第一行包含两个整数 n 和 m ( 1<=n,m<=100 ) — 价格标签的数量（等于阿肖特出售的不同种类水果的数量）和瓦列拉清单上的商品数量。第二行包含 n 个用空格分隔的正整数。每个数都不超过 100，表示某种水果的价格。接下来的 m 行包含清单上的水果名称。每个名称都是一个小写拉丁字母的非空字符串，长度不超过 32。保证清单上的不同水果数量小于或等于 n。还知道卖家有瓦列拉想要购买的所有水果库存。

输出格式

打印两个数字 a 和 b ( a<=b ) — 瓦列拉可能需要购买清单上所有水果的最小和最大总和。

代码题解内容：

思路：

将水果价格排序，然后将需要购买的水果按字典序排序，依次乘上对应的价格即可得到最小值。最大值同理，只不过将需要购买的水果按字典序的逆序排序即可。

代码示例：

# 输入价格和水果名称
prices = list(map(int, input().split()))
fruits = [input() for _ in range(int(input().split()[1]))]

# 排序价格和水果名称
prices.sort()
fruits.sort()
fruits_reversed = fruits[::-1]

# 计算最小和最大花费
min_price = sum([prices[i] * fruits.count(fruits[i]) for i in range(len(prices))])
max_price = sum([prices[i] * fruits_reversed.count(fruits_reversed[i]) for i in range(len(prices))])

# 输出结果
print(min_price, max_price)