目录

D题 Kevin逛超市

题目描述

输入描述:

输出描述:

输入

输出

说明

思路：

代码：

Take that money, and watch it burn\sf Take\ that\ money,\ and\ watch\ it\ burnTake that money, and watch it burn

Sink in the river, the lessons I’ve learned\sf Sink\ in\ the\ river,\ the\ lessons\ I’ve\ learnedSink in the river, the lessons I’ve learned

       —— Counting Stars, OneRepublicCounting\ Stars,\ \text{OneRepublic}Counting Stars, OneRepublic

两个版本唯一的不同是：简单版本中折扣券和立减券的数量均为 111，困难版本中折扣券和立减券的数量为给定值。

氧气少年在逛超市。 他总共买了 nnn 件商品，第 iii 种商品的价格为 pip_ipi​。 超市有下面的打折政策：

请求出氧气少年可能付出的最小的花费。

示例1

这道题就是一个简单的贪心，因为对于商品使用优惠券只有两种情况，要么使用折扣卷，要么使用立减卷，并且对于折扣卷来说，如果他的价值越高，折扣越多，所以优先对于价值高的物品使用折扣卷，然后对于立减卷来说，如果这个物品价值都高于他，那么他的作用是等同的，如果这个物品价值低于他，越高的物品价值，省去的钱越多。

所以通过这里分析可知，我们应该对价格高的（a+b）个物品使用优惠券，枚举这a+b个商品，不管优惠券数量，每个商品选择最优的优惠券使用，如果某个优惠券数量用多了(不妨设是x类型用多了)，则考虑把一部分使用x类型的商品改为使用y类型，怎么改呢，这里又是一个贪心，把所有使用x类型优惠券的商品按“使用y的优惠减去使用x的优惠”排序，相当于如果算出改变这些商品使用的优惠券类型，带来的增量是多少，然后优先选择增量小的就行，直到优惠券数量平衡。