分数: 600 点
问题陈述
给你一个整数序列 A 长度 N 和一个整数 K。 您将对此序列执行以下操作 Q 次:
- 选择长度连续的子序列 K,然后删除其中最小的元素 所选子序列中包含的 K 元素(如果有多个此类元素,请选择其中一个)。
让 X 和 Y 是删除的最大和最小元素的值 Q 操作。你想要 X-Y 尽可能小。 找到最小的可能值 X-Y 当 Q 操作以最佳方式执行。
约束
- 1 \leq N \leq 2000
- 1 \leq K \leq N
- 1 \leq Q \leq N-K+1
- 1 \leq A_i \leq 10^9
- 输入中的所有值都是整数。
输入
输入由标准输入按以下格式给出:
N K Q A_1 A_2 ... A_N
输出
打印最小可能值 X-Y.
示例输入 1
5 3 2 4 3 1 5 2
示例输出 1
1
在第一个操作中,取长度连续的子序列 3 我们选择,里面的最小元素是 1。 因此,第一个操作删除了 A_3=1 现在我们有 A=(4,3,5,2)。 在第二次操作中,最优选择 (A_2,A_3,A_4)=(3,5,2) 作为长度的连续子序列 3 并删除 A_4=2。 在这种情况下,删除的最大元素是 2,最小的是 1,所以他们的区别是 2-1=1.
示例输入 2
10 1 6 1 1 2 3 5 8 13 21 34 55
示例输出 2
7
示例输入 3
11 7 5 24979445 861648772 623690081 433933447 476190629 262703497 211047202 971407775 628894325 731963982 822804784
示例输出 3
451211184