You have $n$ sticks of arbitrary lengths, not necessarily integral.
By cutting some sticks (one cut cuts one stick, but we can cut as often as we want), you want to get $k<n$ sticks such that:
- All these $k$ sticks have the same length;
- All $k$ sticks are at least as long as all other sticks.
Note that we obtain $n + C$ sticks after performing $C$ cuts.
What algorithm would you use such that the number of necessary cuts is minimal? And what is that number?
As an example, take $k=2$ and any $n\geq 2$. The following algorithm can be used:
- Order the sticks by descending order of length such that $L_1\geq L_2 \geq \ldots \geq L_n$.
- If $L_1\geq 2 L_2$ then cut stick #1 to two equal pieces. There are now two sticks of length $L_1 / 2$, which are at least as long as the remaining sticks $2 \ldots n$.
- Otherwise ($L_1 < 2 L_2$), cut stick #1 to two unequal pieces of sizes $L_2$ and $L_1-L_2$. There are now two sticks of length $L_2$, which is longer than $L_1-L_2$ and the other sticks $3 \ldots n$.
In both cases, a single cut is sufficient.
I tried to generalize this to larger $k$, but there seem to be a lot of cases to consider. Can you find an elegant solution?