Greedy algorithm: Minimizing the maximum of a list 
Given a list $L$ of positive integers, assuming you can only modify the list by "splitting" its numbers a finite number $n$ of times. Write an algorithm which minimize the maximum of the last generated list.

By "splitting" a number $x$ I mean deleting $x$ from $L$ and adding to $L$ two positive numbers $\alpha,\beta$ verifying $\alpha+\beta=x$. We can only do this $n$ times.
My try was taking the two greatest elements of $L$, $\alpha$ (the maximum) and $\beta$ (the other), then I split $\alpha$ into $c=\min(\alpha/\beta+1,n+1)$ equal parts (the last part will be $\frac{\alpha}{(\alpha/\beta+1)}+\alpha\text{mod}(\alpha/\beta+1)$). So I spend $c$ of the hability.
Then I repeat the process until I run out of the hability or $\beta=1$, so then y take $c=\min(\alpha/\beta+1,n+1)-1$.
I know my try is not correct, as the list $(10, 4, 9)$ for $n=4$ is a counterexample. Any idea?
 A: Here are a few observations:
1) The order in which you split the integers doesn't matter. In fact the only decision that matters is how many times you will split each integer (or its children): if $a$ is one of the integers in your starting list $L$ and you know you will split $a$ or its children $k$ times, the optimal splitting is to create $k+1$ children of value $\lfloor \frac{a}{k+1}\rfloor +\{0,1\}.$
2) Therefore one naive algorithm is to dole out the $n$ splits in all possible ways to the $|L|$ entries of your original list. There are $\frac{(n+|L|-1)!}{n!(|L|-1)!}$ such ways. For each way, perform the optimal splitting of the entries as in 1) above.
3) But we can do much better. Let's ask a different problem: if I gave you a maximum $m$, how many splits $n$ would be needed to achieve a maximum of $m$? For each entry $a \in L$, we need enough splits $k$ so that $\frac{a}{k+1} \leq m$, or $(k+1)\geq \frac{a}{m}$. Therefore we need at least
$$n_\mathrm{opt}(m) = \sum_{a\in L} \Big \lceil\frac{a}{m}\Big\rceil-1$$
splits to achieve a maximum of $m$.
So our final algorithm proceeds as follows: we will perform a binary search on the value of $m$. We first bracket $m$ in some interval $[l,u]$ with $n_{\mathrm{opt}}(l) > n$ and $n_{\mathrm{opt}}(u) < n$. For example we can use $l=1$ and $u=\max_{a\in L} a$.
We then repeatedly cut the interval in half by testing $m=\lfloor\frac{l+u}{2}\rfloor$ and replacing $l$ or $u$ with this midpoint, accordingly. 
One slight complication is that we are really looking for the boundary between $n_{\mathrm{opt}} = n$ and $n_{\mathrm{opt}} > n$, so terminating the binary search requires a little bit of care, the details of which I leave to you.
This whole procedure runs in time $O(|L|\log M)$, where $M=\max_{a\in L} a$.
