Merging Piles in Any Order
n piles of stones are given by their sizes. Repeatedly choose ANY TWO piles and merge them,
at a cost equal to the sum of the two. Keep going until one pile remains.
Print the smallest possible total cost.
piles 4 3 2 6 -> 29
piles 1 2 -> 3
one pile of 7 -> 0 nothing to merge
## The one word that changes everything
Problem 555 is this problem with ADJACENT in place of ANY TWO, and it needs an interval table
costing O(n^3). Here n reaches 200000, so no table of pairs or intervals is even
representable.
Adjacency was doing all the work. Once any two piles may be merged, the arrangement carries no information at all: only the multiset of sizes matters.
Reading the constraints alongside the earlier problem is what points at this. When the same question appears with a bound raised from hundreds to hundreds of thousands, some restriction has usually been dropped.
## Always merge the two smallest
Keep the piles in a min-heap. Repeatedly remove the two smallest, add their sum to the total, and push the sum back.
## Why that is optimal
Think of the merge history as a binary tree whose leaves are the original piles. A pile at
depth d is included in exactly d merges, so
total cost = sum over piles of size * depth
To make that small, the BIGGEST piles need the SMALLEST depths, which means the smallest piles must sit deepest. In any tree the two deepest leaves are siblings, so there is an optimal tree in which the two smallest piles are siblings. Merging them first and treating the result as a single pile leaves the same problem with one fewer pile, and the argument repeats.
That is the standard exchange argument, and it is the reason this is a greedy rather than a guess. It is exactly the construction behind Huffman coding, which is the same problem in different clothing.
## The practical trap
The intermediate sums grow, so they must go back into the heap as ordinary values and compete on equal terms. Sorting once and walking the list in order is NOT the same algorithm: a merged pile can be larger than several originals, and it has to sink back to its proper place.
On 1 2 3 4 5 a sort-once pass gives 34 and the heap gives 33, so the input is in the tests.
## Overflow
The total reaches about sum * log n, which at these limits is near 4 * 10^15. Use 64 bits.
In JavaScript that is still exact in a double, since it is below 2^53.
## Boundaries
A single pile costs 0: there is nothing to merge. Two piles cost their sum, once.
## Cost
Time O(n log n). Space O(n).