Divide Chocolate

Problem A chocolate bar has n contiguous chunks with sweetness values. Make k cuts to produce k+1 contiguous pieces; you keep the piece with the minimum total sweetness. Maximize the sweetness of the piece you keep.

Input / Output

• Input: int array sweetness, int k.
• Output: the maximum achievable minimum-piece total.

Constraints

• 0 <= k < n <= 10^4; values up to 10^5 — O(n log Σ) expected.

Example

• sweetness = [1,2,3,4,5,6,7,8,9], k = 5 → 6 (pieces [1,2,3], [4,5], [6], [7], [8], [9]).

Expected approach

• Binary search on the answer X: greedily sweep, cutting a piece whenever its running sum reaches X; if we can form ≥ k+1 pieces, X is feasible. Search the largest feasible X in [min(sweetness), Σ/(k+1)]. O(n log Σ) time, O(1) space. This "max-min via binary search + greedy feasibility" pattern (Split Array Largest Sum is the min-max twin) is the real thing being tested.