Spread the Routers
Place C routers on N possible positions along a corridor so that the minimum distance between any two routers is as large as possible. Print that distance.
Input: the first line has N and C; the second line has the N positions.
Output: the largest achievable minimum pairwise distance.
Constraints:
- 2 ≤ C ≤ N ≤ 105
- 0 ≤ positions ≤ 109
Sample Tests
Input 1
5 3 1 2 8 4 9
Output 1
3
Input 2
2 2 5 5
Output 2
0
Discussion (opens after you solve — no spoilers before)
No comments yet.