← 返回题目列表

AtCoder · awc0075_d

D. 分类花束

中文机器翻译题面 查看原题

分数: 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