分数: 400 分
问题陈述
高桥在一家花店兼职。今天他被分配了排序的任务 N 花成 K 花束。
每朵花 i (1 \leq i \leq N) 有一个整数 A_i 代表其“茎长度”。全部 N 鲜花必须准确地分配给其中之一 K 花束。然而,每束鲜花的数量必须介于 0 和 M,包括在内。花束中完全不含鲜花是可以接受的。
如果同一束花中的花朵茎长差异较大,则花束看起来没有吸引力。因此,高桥想要使用非负整数对花进行排序,以满足以下条件 D:
- 对于每束包含 2 或多朵花,该花束中花的最大茎长度与最小茎长度之差最多为 D.
对于含有以下成分的花束 0 or 1 花,这个条件自动满足。
较小 D 是,每束花看起来越好,但如果 D 太小,可能无法将所有花分类到 K 花束。另一方面,如果 D 足够大,最多只有容量限制 M 需要考虑每束鲜花,因为 K \times M \geq N 保证,总是可以对鲜花进行排序。
找到最小值 D 这样就可以分配所有 N 鲜花到 K 花束同时满足上述条件。既然所有 A_i 是整数,答案也是非负整数。
约束
- 1 \leq N \leq 2 \times 10^5
- 1 \leq K \leq N
- 1 \leq M \leq N
- K \times M \geq N
- 1 \leq A_i \leq 10^9
- 所有输入值均为整数。
输入
N K M A_1 A_2 \ldots A_N
- 第一行包含三个空格分隔的整数: N 代表鲜花的数量, K 代表花束的数量,以及 M 代表每束鲜花的最大数量。
- 第二行包含空格分隔的整数 A_1, A_2, \ldots, A_N 代表每朵花的茎长。
输出
在一行中打印以下值的最小值 D 这样所有 N 满足条件即可分配鲜花。
示例输入 1
5 2 3 1 3 5 8 10
示例输出 1
4
示例输入 2
4 2 2 1 5 10 20
示例输出 2
10
示例输入 3
10 3 4 2 5 8 11 15 20 25 30 33 37
示例输出 3
10
示例输入 4
20 5 5 3 7 12 18 25 31 38 42 50 55 63 70 78 85 90 96 100 108 115 120
示例输出 4
20
示例输入 5
1 1 1 1000000000
示例输出 5
0