Codeforces Round #727 PriceFixed Solution (Java/C++)

Solution:

For each product, we will buy exactly $a_i$ items. We will not buy more items. So, the total number items we buy will not change (because the purpose to buy more is discount, but the benefit of discount is same with the cost of one item).
So, the problem is transferred to put each item to each position. If the b is less than the index, then this item can get discount.
For example, the sample 2:

So, we know that, for b=4, index need to greater than 5. For b=2, index need to greater than 3. So, we need some items to fill in the positions of subscripts 1, 2, and 4. Obviously, we choose the item with largest b to do this.

We consider whether we can get a discount for products one by one from small to large by filling some product with higher b.

Code:

Java

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

C++

Submission #120137395 - Codeforces
Codeforces. Programming competitions and contests, programming community
Show Comments
DigitalOcean Referral Badge