251. Smallest Capacity That Works
n packages must be shipped within D days. They must go in the order
given, and each day you load packages onto the ship until the next one would
exceed its capacity.
Print the smallest capacity that gets everything shipped within D days.
The answer is not something you can compute directly, and you can TEST a
capacity easily: walk the packages, count the days it would take, and compare
with D. And if a capacity works, every larger one works too.
That monotonic property is exactly what binary search needs, so search over the answer rather than over the data. This pattern, sometimes called binary search on the answer, turns a large family of "smallest value that works" problems into a check plus a halving.
Constraints - `1 ≤ D ≤ n ≤ 200000` - `1 ≤ weight ≤ 500`
Input
The first line contains two integers n and D.
The second line contains n package weights in loading order.
Output
Print one integer, the smallest capacity that ships everything within D days.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.