Editorial for COCI '12 Contest 2 #4 Popust

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.

What does an optimal solution for a given $K$ ~K~ look like? There are two possibilities:

$K-1$ ~K-1~ meals with the lowest $B$ ~B~ price and one meal with the lowest $A$ ~A~ price (out of the remaining meals)
$K$ ~K~ meals with the lowest $B$ ~B~ price, where one of them is chosen as first (subtracting its $B$ ~B~ price and replacing it with the $A$ ~A~ price – obviously, the one with the lowest $A_i-B_i$ ~A_i-B_i~)

Let us sort the meals by ascending $B$ ~B~ prices and solve the problem incrementally for $K = 1, 2, \dots, N$ ~K = 1, 2, \dots, N~. We will keep the current sum of $B$ ~B~ prices for the first $K-1$ ~K-1~ meals (sorted by $B$ ~B~). Also, using a structure (such as a C++ STL set) we will keep the remaining, unselected, meals sorted by $A$ ~A~ (to be able to find the price of the first case), and another structure will keep the selected meals, sorted by $A_i-B_i$ ~A_i-B_i~ (to be able to find the price of the second case). The total complexity is $\mathcal O(N \log N)$ ~\mathcal O(N \log N)~ if a structure query takes $\mathcal O(\log N)$ ~\mathcal O(\log N)~ time.

Comments

There are no comments at the moment.