已结束 IOI

测试

开始2026-11-15 13:00:00 → 结束2026-11-16 13:00:00 · 参赛2 人
比赛 --:--:--
服务器时间 2026-11-19 21:09:54

M. 愤怒的牛

描述

农夫约翰建造了一座有 n 间牛舍的小屋,牛舍排在一条直线上,第 i 间牛舍位于坐标 x_i 处。约翰有 m 头牛,它们经常互相攻击,因此约翰决定把每头牛都安排在尽可能远离其他牛的牛舍中,即要最大化任意两头牛之间的最小距离。

请你帮助约翰确定这个最大的最小距离是多少。

输入

第一行包含两个整数 n 和 m ( 2 \le m \le n \le 100000 ),分别表示牛舍的数量和牛的数量。

第二行包含 n 个整数 ( x_1, x_2, \dots, x_n ),( 0 \le x_i \le 10^{10} ),表示每个牛舍的位置,位置不一定有序。

输出

输出一个整数,表示最大的最小距离。

样例

输入

5 3
1 2 8 4 9

输出

3

提示

样例说明

将 3 头牛放在位置 1、4、9(或 1、4、8)等,最小距离为 3,且无法得到更大的最小距离(如距离 4 无法放下 3 头牛)。

数据范围与约定

  • 2 \le m \le n \le 100000
  • 0 \le x_i \le 10^{10}

Submit

登录

注册
时间限制 1 秒
内存限制 128 MB
提交