1358: Aggressive cows 愤怒的牛

Memory Limit:128 MB Time Limit:1.000 S
Judge Style:Text Compare Creator:
Submit:38 Solved:33

Description

约翰有N 间牛棚,这些牛棚坐落在一条直线上,第i 间牛棚位于坐标Xi 的位置。他要把C 头 奶牛安排在这些牛棚里。每间牛棚最多可以放一头奶牛,也可以空着。这些奶牛的脾气都很暴燥,所以把它们分得越远越好。请你帮助约翰安排这些奶牛的住处,使得她们两两之间的最短距离最大。

Input

第一行:两个整数N 和C,2 ≤ C ≤ N ≤ 105
第二行和第N + 1 行:一个整数Xi,0 ≤ Xi ≤ 109


Output

单个整数:最大的最小距离

Sample Input Copy

5 3
1
2
8
4
9

Sample Output Copy

3

HINT

它是求最小值最大的问题。每两头牛之间的最小距离为 d ,也就是每两头牛之间的距离 >= d ,问题也就是求这个 d 最大是多少。
1.对所有的牛舍从小到大排序。
2.假设我们把第 i 头牛放在 ai 号牛舍里,那么第 i+1 头牛就要放在 ai+d<=ak 的ak 牛舍中,由于可能有很多牛舍满足条件,我们 选取距离 ai 最近的一个,然后依次类推,放牛。

Source/Category