题目思路

由于优惠券只能选一个，所以肯定选择需要购买数量最少的，然后选择最大那几个作为优惠券使用的目标，这样就可以让减免的书籍的价格最大化。

时间复杂度$O(n)$

代码

Java

问题描述

小红在商店中选购了 $n$ 件商品，每件商品的价格分别为 $P_1, P_2, ..., P_n$。商店提供了 $m$ 张优惠券，每张优惠券对应可以减免特定数量商品中价格最低者的金额。每张优惠券标注了一个数字 $a_i$，表示使用该优惠券时需选购恰好 $a_i$ 件商品进行折扣。小红只能使用一张优惠券，求小红如何选择使用优惠券以使得总花费最小。