To keep grazing cows at the campus farm from fighting, Arif (who also volunteers there) must place them in stalls to MAXIMIZE the minimum distance between any two cows. Given N stall positions and C cows, place all C cows into stalls to MAXIMIZE the minimum distance between any two cows. Binary search on the answer (the minimum distance), with a greedy feasibility check placing cows one by one.
Input
Line1: N C. Line2: N stall positions.
Output
The maximized minimum distance.
Constraints
2 ≤ C ≤ N ≤ 10^5
Sample Input
5 3 1 2 4 8 9
Sample Output
3
main.c
Loading editor…
Write C, then Run (custom I/O) or Submit (sample tests). ⌘/Ctrl+Enter submits.