Codeforces Round #727 PriceFixed 题解 (Java/C++)

题解

显然，对于每种商品，我们一定是恰好买a个，不会多买。也就是买的商品总数不会变（因为多买无非是为了凑折扣，但多买一个的代价正好等于折扣的好处）。
于是我们可以考虑把每个商品放到不同的位置，只要这个商品对应的b值小于他的位置则可以打折。
以样例2为例：

于是我们知道，对于b=4来说，需要商品的下标大于等于5。而对于b=2来说，只需要大于等于3。于是我们需要有商品来填充下标1、2、4的位置。这个时候，显然是优先选择b值较大的来充数。

于是我们按照b值从小到大依次考虑是否能通过往前面填充一些b较高的商品来获取打折即可。

代码

Java

C++