919. Splitting the Workers to Build the Blocks

One worker must build n blocks. Block i takes t[i] time to build. At any moment a worker may do exactly one of two things:

build one block takes that block's time, and the worker then stops split into two workers takes exactly s time, after which both workers are free to do either thing

Workers act in parallel. Print the least time until every block is built.

``` blocks 1 2 3, s = 5 -> 12 split (5), then one worker splits again (5 more, so at time 10) and the two resulting workers build the 1 and the 2, finishing at 11 and 12; the other original worker builds the 3, finishing at 8. Total 12.

one block of 7, s = anything -> 7 no split is needed

two blocks of 1, s = 1 -> 2 ```

## What most people try first

Searching over split trees is enormous: the number of shapes is the Catalan number, so even n = 15 gives 9694845 arrangements before assigning blocks.

Sorting the blocks and splitting greedily "when a worker has more than one block left" does not say which blocks go where, and the wrong assignment costs more.

## The method: combine the two SHORTEST blocks

h = min-heap of all block times while h has more than one entry: x = pop; y = pop push max(x, y) + s print the single entry left

This is the same shape as joining ropes in problem #867, and the combine rule is the entire difference.

#867 joining ropes combined value = x + y and the total is summed here combined value = max(x, y) + s

## Why the combine rule is what it is

Think of the process backwards. A worker who is going to build two blocks, taking x and y, must first split, which costs s, and then the two halves run in PARALLEL. So that worker finishes at s + max(x, y), and from the outside the pair behaves exactly like a single block of time max(x, y) + s. Replacing the pair by that value leaves an instance with one fewer block whose answer is the same.

## Why the two shortest

Suppose the two blocks combined at the deepest level of some optimal tree are not the two shortest. Then some shorter block sits at a shallower level. Swapping them cannot increase the answer: a block's contribution is its time plus s times its depth, and the final answer is the maximum of those contributions, so moving a smaller time deeper and a larger time shallower replaces max(big + deep, small + shallow) by max(small + deep, big + shallow), which is no larger.

Repeating the exchange pushes the two shortest to the deepest level, which is exactly what the heap does on its first step. Induction on the reduced instance finishes the argument.

## The boundary that breaks a careless implementation

With n = 1 the loop never runs and the answer is that block's time, not t[0] + s. Splitting with nothing to split for is never useful and the code must not charge for it.

The combined value is max(x, y) + s, not x + y + s and not max(x, y + s). Using the sum turns this into #867 and gives 11 instead of 12 on the first example.

The combined value goes BACK into the heap and competes with the originals. It is larger than both of its parts, so it will be combined later rather than sooner, which is the property the tree depends on.

## Overflow

Each combine adds s, and the depth of the tree is about log2(n), which is 17 at n = 10^5. So the answer is at most max(t) + 17 * s, which with both at 10^9 reaches about 1.8 * 10^10. The declared test with eight blocks of 10^9 and s = 10^9 lands on exactly 4 * 10^9, which a 32-bit build reports as -1294967296. Use 64 bits.

## Related problems

Problem #867 joins ropes with the sum rule and asks for the accumulated cost; #596 is the same question phrased as merging piles. All three take the two smallest repeatedly, and comparing them is the point: what changes is the combine rule and what is reported, not the structure.

## Cost

Time O(n log n). Space O(n).

Constraints - `1 ≤ n ≤ 100000` - `1 ≤ s ≤ 10^9` - `1 ≤ t[i] ≤ 10^9`