Editorial for Another Contest 5 Problem 3 - Cutting Cheese Costs
Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.
Submitting an official solution before solving the problem yourself is a bannable offence.
Instead of minimizing the amount of money Tudor pays, we will rephrase the
problem as trying to maximize the amount of money Tudor saves, as the total cost
of the cheeses with no discounts is by definition equal to the amount of
money Tudor actually pays plus the amount of money he saves.
If we rephrase the problem in this way, then the problem actually reads as
follows - we have integers and want to compute the sum of the
largest
ones. The most obvious way to do this is to use an
sorting algorithm, which comfortably runs in time.
This can also be done in linear time, though that was not necessary for this problem.
Comments