BN202604 星球探险营地

题目描述

探险队正在一条直线上规划星球探险路线。路线上有 N 个可以搭建营地的位置，第 i 个位置的坐标为 p_i。

探险队需要选择其中的 K 个位置搭建营地，并且希望任意两个相邻营地之间的距离尽可能大。

请你计算：选择 K 个位置后，任意两个相邻营地之间的最小距离最大是多少。

注意：

• 每个位置最多搭建一个营地；
• 营地必须搭建在给出的 N 个位置上；
• 位置坐标已经按照从小到大的顺序给出。

输入格式

第一行包含两个正整数 N 和 K，分别表示可选位置数量和需要搭建的营地数量。

第二行包含 N 个正整数 p_1, p_2, ..., p_N，表示每个可选位置的坐标，且满足：

p_1 < p_2 < ... < p_N

输出格式

输出一个整数，表示任意两个相邻营地之间的最小距离的最大值。

样例输入

6 3
2 5 9 14 18 25

样例输出

11

样例说明

可以选择坐标为：

2、14、25

搭建三个营地。

相邻营地之间的距离为：

14 - 2 = 12
25 - 14 = 11

其中最小距离为 11。

尝试其他选择方案，都不能让三个营地之间的最小距离超过 11，所以答案是 11。

数据范围

• 2 ≤ K ≤ N
• 1 ≤ N ≤ 10^5
• 1 ≤ p_i ≤ 10^9
• p_i < p_{i+1}