883. The Total of the k Cheapest So Far
Price quotes arrive one at a time. After each arrival, print the TOTAL of the
k cheapest quotes received so far. If fewer than k have arrived, print the
total of all of them.
n = 6, k = 3, quotes 7 2 9 1 8 3 -> 7 9 18 10 10 6
n = 4, k = 4, quotes 4 3 2 1 -> 4 7 9 10
n = 7, k = 2, quotes 1 2 3 4 5 6 7 -> 1 3 3 3 3 3 3
Trace the first one. After 7: total 7. After 2: total 9. After 9: the
three cheapest are 7 2 9, total 18. After 1: the three cheapest are
1 2 7, total 10, because the 9 has been pushed out. After 8 nothing
changes. After 3: the three cheapest are 1 2 3, total 6.
Notice that the answer can go DOWN. That is the whole shape of the problem: a cheap arrival does not just get added, it displaces the most expensive survivor.
## What most people try first
Re-sorting the prefix and adding up its first k entries. That is
O(n log n) per line, so O(n^2 log n) in total. Even keeping the first
k in a sorted array and re-summing them each time is O(k) per line, which
at n = k = 200000 is 4 * 10^10 additions.
## The heap, plus one number
This is the max-heap of problem 882, holding the k cheapest, with a running
total carried alongside it. The total changes in exactly two ways:
the heap is not yet full: push v, total = total + v
v is cheaper than the top: total = total + v - top, replace the top
otherwise: nothing changes at all
## Why the running total is safe
The heap's contents change by at most one element per arrival, and the code
knows exactly which element left and which arrived. So the total can be
UPDATED rather than recomputed, and the update is two additions. Recomputing
would be O(k) and would defeat the whole point, in the same way that
recomputing a window sum defeats a sliding window.
The one trap is doing the arithmetic in the wrong order relative to the heap operation. If you pop first and then read the top to subtract it, you have already lost the value you wanted. Read the top, do the arithmetic, then replace.
## Overflow, with the actual magnitude
This is where the 32-bit build finally dies. Two hundred thousand quotes at
10^9 each give a total of 2 * 10^14, against a signed 32-bit ceiling of
2147483647. Even three quotes at 10^9 reach 3 * 10^9, which wraps to
-1294967296, and the three-quote test in this problem is exactly that.
The individual prices fit in 32 bits perfectly well. The TOTAL does not, and the accumulator is the only variable that has to be widened.
## The boundary that breaks a careless implementation
The warm-up lines, before k quotes have arrived. Unlike problem 882 there is
no none here: the answer is the total of what exists, which is a real number
from the very first line. A program that waits for the heap to fill before
printing anything is off by k - 1 lines.
The second boundary is the strict comparison. Replacing on v <= top gives
the same total but does needless work on every tie, and 6 6 6 6 6 with
k = 2 is the test that would expose it in a timing run.
## Related problems
Problem 882 holds the same heap and prints its top. Problem 880 holds the
mirror-image heap for the k largest. Problem 901 uses the same bounded heap
for something that does not look like a total at all: it keeps the l
largest climbs on ladders and pays bricks for everything evicted.
## Cost
Time O(n log k). Space O(k).
Constraints - `1 ≤ k ≤ n ≤ 200000` - `1 ≤ price ≤ 1000000000`
Input
The first line contains two integers n and k.
The second line contains n integers, the quotes in arrival order.
Output
Print n integers on one line, separated by single spaces: after each arrival, the total of the k cheapest quotes so far, or of all of them if fewer than k have arrived.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.