好斗的奶牛
测试数据来自 wjszez/2118
问题描述:
John拥有一个的属于自己的农场。最近,为了提高农场的运营状况,他建了一个有N (2 <= N <= 100,000)个槽的畜棚。这些槽位于一条直线上,其坐标分别为x1,x2,…xN(0≤xi≤1,000,000,000)。
John新购买了一批奶牛,数量为C头。这些奶牛不喜欢槽式生活,并且经常进行一些激烈的打斗。为了减少奶牛们相互伤害而造成的损失,John必须按一定的策略来来安排这些奶牛进入槽。John策略就是,使距离最近的两头奶牛间的距离越大越好。
设D为距离最近的两头奶牛间的距离,请帮住John求出最大的D。
输入格式:
第1行2个数N和C(2<=C<=N)。
接下来N行,每行一个数表示第i个槽的位置xi。
输出格式:
距离最近两头奶牛间的距离的最大值。
样例输入:
5 3
1
2
8
4
9
样例输出:
3
样例提示:
John将他的3头奶牛放入坐标为1、4、9这3个槽类,最近的两头奶牛间的
距离为3.
数据限制:
50%数据保证n<=100
70%数据保证n<=10000
100%数据保证n<=100000
信息
- ID
- 2154
- 难度
- (无)
- 分类
- (无)
- 标签
- 递交数
- 0
- 已通过
- 0
- 通过率
- ?
- 上传者