[ARC098E] Range Minimum Queries
题意翻译
## 题目描述
你有一个长度为 $n$ 的整数序列 $A$,以及一个整数 $K$。你会进行 $Q$ 次操作,一次操作如下:
- 选择序列中一个长度为 $K$ 的区间,并且删除区间中的最小元素。如果有多个,你可以选择任何一个。
现在,设 $X$ 是你删除了的元素中最大的一个,$Y$ 是最小的一个,请找出在最优情况下,$X-Y$ 的最小值。
## 输入格式
请从标准输入中读入:
$ N $ $ K $ $ Q $
$ A_1 $ $ A_2 $ $ ... $ $ A_N $
## 输出格式
请输出 $X-Y$ 可能的最小值。
## 限制
- $1\le K\le N\le 2000$
- $1\le Q\le N-K+1$
- $1\le A_i\le 10^9$
- 输入都是整数
题目描述
[problemUrl]: https://atcoder.jp/contests/arc098/tasks/arc098_c
長さ $ N $ の数列 $ A $ と整数 $ K $ が与えられます。 この配列に、以下の操作を $ Q $ 回行います。
- 長さ $ K $ の連続する部分列を $ 1 $ つ選ぶ。 そして、選んだ部分列に含まれる $ K $ 個の要素のうち最小のもの(複数ある場合はその中で好きなものを $ 1 $ 個)を取り除く。
$ Q $ 回の操作で取り除いた要素の最大値、最小値をそれぞれ $ X $, $ Y $ としたときに、$ X-Y $ をできるだけ小さくしたいです。 $ Q $ 回の操作を適切に行ったときの $ X-Y $ の最小値を求めてください。
输入输出格式
输入格式
入力は以下の形式で標準入力から与えられる。
> $ N $ $ K $ $ Q $ $ A_1 $ $ A_2 $ $ ... $ $ A_N $
输出格式
$ X-Y $ の最小値を出力せよ。
输入输出样例
输入样例 #1
5 3 2
4 3 1 5 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
说明
### 制約
- $ 1\ \leq\ N\ \leq\ 2000 $
- $ 1\ \leq\ K\ \leq\ N $
- $ 1\ \leq\ Q\ \leq\ N-K+1 $
- $ 1\ \leq\ A_i\ \leq\ 10^9 $
- 入力はすべて整数である
### Sample Explanation 1
$ 1 $ 回目の操作では、どの長さ $ 3 $ の連続する部分列を選んでも、そのうち最小の要素は $ 1 $ です。 よって、$ 1 $ 回目の操作によって $ A_3=1 $ が取り除かれ、$ A=(4,3,5,2) $ となります。 $ 2 $ 回目の操作では、連続する長さ $ 3 $ の部分列として、$ (A_2,A_3,A_4)=(3,5,2) $ を選び、$ A_4=2 $ を取り除くのが最適です。 この場合、取り除いた要素の最大値は $ 2 $、最小値は $ 1 $ になるので、その差は $ 2-1=1 $ になります。