933. Selling the Stock at Falling Prices

A warehouse holds n piles of identical goods, the ith with a[i] units. Selling one unit from a pile that currently holds x units earns exactly x rupees, and the pile then holds x - 1.

Exactly orders units must be sold. Print the largest total earned. It is guaranteed that orders does not exceed the total number of units.

piles 2 5, orders 4 -> 14 sell at 5, 4, 3 from the second pile and at 2 from the first piles 2 2 2, orders 3 -> 6 sell one from each at price 2 one pile of 10^9, orders 10^9 -> 500000000500000000

## The heap answer, and why it loses

The greedy is obviously right: always sell from the biggest pile, because the price IS the pile size, so the largest available price is the pile top. Nothing subtle there.

The obvious implementation is a max-heap:

repeat orders times: x = pop the largest; total = total + x; push x - 1 if positive

That is O(orders log n). And orders reaches 10^9, so it is about 10^9 * 17 = 1.7 * 10^10 heap operations. Measured on the third example above, a single pile of 10^9 with 10^9 orders, the heap version takes about 160 seconds in Python. The method below takes under a millisecond on the same input.

The heap is not wrong. It is a per-unit loop when the input describes the units in bulk, and the fix is to stop enumerating and start counting.

## The method: sell a whole TIER at once

Sort the piles descending. At any moment the piles that are tied at the current top price form a block, and all of them fall together to the next distinct price below.

sort a descending i = 0, cur = a[0], left = orders, total = 0 while left > 0 and cur > 0: extend i while a[i+1] equals cur (width = i + 1 piles at cur) nxt = a[i+1] if it exists, else 0 drop = cur - nxt block = width * drop units sold to bring the whole tier down to nxt if block <= left: total = total + width * (cur + nxt + 1) * drop / 2 left = left - block cur = nxt; advance i else: full = left / width whole rounds affordable total = total + width * (cur + cur - full + 1) * full / 2 rem = left - full * width leftovers, one each total = total + rem * (cur - full) left = 0 print total

Each iteration either consumes one distinct pile value or finishes, so the loop runs at most n times whatever orders is.

## Why the arithmetic is a series, not a loop

Selling width piles down from cur to nxt + 1 sells each price in nxt+1 ... cur exactly width times. The total of consecutive integers from lo to hi is (lo + hi) * (hi - lo + 1) / 2, which with lo = nxt + 1 and hi = cur gives (cur + nxt + 1) * drop / 2.

The partial case is the same series stopped early, plus a final row of rem units all sold at the same price cur - full, since after full complete rounds every pile in the tier holds cur - full.

## The boundary that breaks a careless implementation

The remainder row sells at cur - full, not cur - full + 1. After full complete rounds a pile holds cur - full, and the next unit sold from it earns that. Getting this wrong shifts every partial answer by rem.

The division by 2 is exact because (cur + nxt + 1) and drop are consecutive in parity: one of them is always even. Doing the division before the multiplication can still lose a half, so multiply first.

The loop stops when cur reaches 0 as well as when left does. Without that guard, a request for more units than exist spins forever, and the guarantee in the statement is what makes the second condition unnecessary in practice rather than something to rely on.

## Overflow

This is where 64 bits stops being enough to be casual about. One pile of 10^9 sold to exhaustion earns 10^9 * (10^9 + 1) / 2 = 500000000500000000, which is 5 * 10^17. With orders at 10^9 and prices at 10^9 the answer is bounded by 10^18, which a signed 64-bit integer holds, since it goes to about 9.2 * 10^18.

The intermediate products need the same care: width * (cur + nxt + 1) reaches 10^5 * 2 * 10^9 = 2 * 10^14, and multiplying by drop up to 10^9 would reach 2 * 10^23 if the whole tier were consumed at once, but block <= left caps the units sold at 10^9, so the product is bounded by the answer itself. A 32-bit build fails on almost every test here.

## Related problems

Problem #926 makes the same move in the opposite direction: there the bounded VALUE range replaces a heap with a count array. Here the bounded NUMBER OF DISTINCT values replaces a per-unit loop with a per-tier one. Both are the same instinct, which is to ask what the input is really describing before choosing a structure to walk it with.

## Cost

Time O(n log n) for the sort, then O(n). Space O(n).

Constraints - `1 ≤ n ≤ 100000` - `1 ≤ a[i] ≤ 10^9` - `1 ≤ orders ≤ 10^9` and `orders` is at most the total number of units