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

题解

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

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

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

代码

Java

Submission #120134526 - Codeforces
Codeforces. Programming competitions and contests, programming community

C++

Submission #120137395 - Codeforces
Codeforces. Programming competitions and contests, programming community
展示评论