1119. Joining the Dearest First

You have n ropes. Joining two ropes costs the sum of their lengths and leaves one rope of that combined length, which can be joined again. Keep going until a single rope remains.

Print the LARGEST total cost you can run up.

ropes 1 2 3 4 -> 26 ropes 99 -> 0 nothing to join ropes 5 7 -> 12 the only join ropes 1 1 1 -> 5

Trace the first line. Join 4 and 3 for 7, join 7 and 2 for 9, join 9 and 1 for 10. The total is 7 + 9 + 10 = 26. Joining the two shortest first gives 3 + 6 + 10 = 19, which is the smallest possible and is problem #867's question.

## What most people try first

Adding up the lengths and multiplying by something. There is no such formula, because the answer depends on the shape of the join tree and not only on the total.

The second instinct is that the answer is the same whatever order is used, since every rope ends up in the final rope anyway. That is false, and the two numbers above prove it: 26 against 19 on the same four ropes.

## Where the cost really comes from

Every join charges the combined length of the two pieces, which is the total of all the ORIGINAL ropes inside them. So each original rope of length L contributes L once for every join it takes part in, directly or through a piece containing it. That number is exactly the DEPTH of that rope's leaf in the join tree.

total cost = sum over ropes of length * depth in the join tree

To make the total large, give the long ropes large depths.

## The method

Always join the two LONGEST ropes available.

put every length into a max-heap total = 0 while the heap holds more than one: x = pop, y = pop total = total + x + y push x + y

n pushes and n pops, so O(n log n).

The joined piece goes back in and competes with the rest, which is why a single sort is not enough: the piece made by the first join is longer than everything and must be part of the next one.

## Why the two longest is right

Consider any join tree and look at a deepest join, the one whose two children are both original ropes at the maximum depth. Suppose it joins ropes x and y while some rope z longer than x sits at a strictly smaller depth. Swap z with x.

The total changes by (depth(x) - depth(z)) * (z - x). The first factor is positive because x was deeper, and the second is positive because z is longer. So the total grows, and no tree in which a longer rope sits shallower than a shorter one can be maximal.

That says the depths must be assigned in decreasing order of length, and building the tree by repeatedly joining the two longest does exactly that: the two longest are the first to be buried and end up deepest.

## The boundary that breaks a careless implementation

A single rope answers 0. The loop must be guarded by "more than one remains", not by "the heap is not empty", or the first pop on a one-element heap reads nothing.

Lengths of 0 are allowed and simply contribute nothing.

Most heap libraries give a MIN-heap. Negating every value on the way in and out turns one into a max-heap, which is worth knowing because it avoids writing a second implementation.

## Sizes

n reaches 1000 and a length reaches 10^9, so the total of all ropes reaches 10^12 and the answer, which is bounded by that total times the number of joins, reaches about 10^15. That is far past the 2147483647 limit of a signed 32-bit integer, and three ropes of 10^9 already cost 5 * 10^9, which the eighth test checks.

## A related problem

Problem #867 is this operation with the objective flipped: join the two SHORTEST and get the smallest total, which is Huffman's algorithm. Problem #1120 stops after a fixed number of joins instead of going all the way to one rope.

Constraints - `1 ≤ n ≤ 1000` - `0 ≤ length ≤ 1000000000`