题目描述The spring is coming and it means that a lot of fruits appear on the counters One sunny day little boy Valera decided to go shopping He made a list of mm fruits he wanted to buy If Valera want to

算法1

(哈希表) $O(m)$

首先读入每种水果的价格，然后将其存储在哈希表中，键为水果名，值为价格。

然后遍历Valera的购物清单，将每种水果的价格累加起来，即可得到购物清单的总价。

为了求最小和最大总价，需要对哈希表中的价格按照从小到大排序，然后依次将最小的价格分配给购物清单中每种水果，将最大的价格分配给购物清单中数量最多的水果。

时间复杂度

读入价格需要 $O(n)$ 的时间，遍历购物清单需要 $O(m)$ 的时间，排序需要 $O(n \log n)$ 的时间，分配价格需要 $O(m)$ 的时间，因此总时间复杂度为 $O(n \log n + m)$。

空间复杂度

哈希表所需空间为 $O(n)$，因此总空间复杂度为 $O(n)$。

C++ 代码

算法2

(计数排序) $O(n+m)$

由于价格不超过100，可以使用计数排序。首先读入每种水果的价格，然后将其存储在计数数组中，下标为价格，值为该价格的水果种类数量。然后遍历Valera的购物清单，将每种水果的价格累加起来，即可得到购物清单的总价。为了求最小和最大总价，需要从计数数组中依次取出最小的价格和最大的价格，然后依次将最小的价格分配给购物清单中每种水果，将最大的价格分配给购物清单中数量最多的水果。

时间复杂度

读入价格需要 $O(n)$ 的时间，遍历购物清单需要 $O(m)$ 的时间，计数排序需要 $O(n)$ 的时间，分配价格需要 $O(m)$ 的时间，因此总时间复杂度为 $O(n+m)$。

空间复杂度

计数数组所需空间为 $O(100)$，因此总空间复杂度为 $O(1)$。

C++ 代