259. Spread Them Out
There are n positions on a line and you must place c items on them, at
most one per position. Print the largest possible value of the smallest gap
between any two chosen positions.
You cannot compute this directly. You CAN test a gap d: sort the positions,
take the first, and greedily take the next position at least d beyond the
last one taken. If that places c or more items, d is achievable.
And if d works, every smaller gap works too. So the achievable gaps form a
prefix, and binary search finds where it ends.
This is the same shape as problem 251, with one difference worth noticing: here you want the LARGEST value that works rather than the smallest, so the search rounds its midpoint up instead of down.
Constraints - `2 ≤ c ≤ n ≤ 200000` - `0 ≤ position ≤ 1000000000` - All positions are distinct.
Input
The first line contains two integers n and c.
The second line contains n distinct positions in any order.
Output
Print one integer, the largest achievable minimum gap.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.