由于优惠券只能选一个,所以肯定选择需要购买数量最少的,然后选择最大那几个作为优惠券使用的目标,这样就可以让减免的书籍的价格最大化。
时间复杂度O(n)
Java
小红在商店中选购了 n 件商品,每件商品的价格分别为 P1,P2,...,Pn。商店提供了 m 张优惠券,每张优惠券对应可以减免特定数量商品中价格最低者的金额。每张优惠券标注了一个数字 ai,表示使用该优惠券时需选购恰好 ai 件商品进行折扣。小红只能使用一张优惠券,求小红如何选择使用优惠券以使得总花费最小。
第一行包含两个正整数 n,m,分别表示商品的数量和优惠券的数量。
第二行包含 n 个空格分隔的正整数 P1,P2,...,Pn,表示每件商品的价格。
第三行包含 m 个空格分隔的正整数 a1,a2,...,am,表示每张优惠券对应的商品数量。
输出一行一个整数,表示小红使用优惠券后的最小总花费。
3 2
90 30 40
2 3
120
对于所有评测数据,满足 1<n,m<50000,1≤ai≤n,1≤Pi≤104。