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)$ $O (N \log N)$ if a structure query takes $\mathcal O(\log N)$ $O (\log N)$ time.

Comments

There are no comments at the moment.