103612: [Atcoder]ABC361 C - Make Them Narrow
Memory Limit：256 MB
Time Limit：2 S
Judge Style：Text Compare
Creator：
Submit：10
Solved：0
Description
Score : $250$ points
Problem Statement
You are given a sequence $A$ of length $N$.
Freely choose exactly $K$ elements from $A$ and remove them, then concatenate the remaining elements in their original order to form a new sequence $B$.
Find the minimum possible value of this: the maximum value of $B$ minus the minimum value of $B$.
Constraints
- All inputs are integers.
- $1 \le K < N \le 2 \times 10^5$
- $1 \le A_i \le 10^9$
Input
The input is given from Standard Input in the following format:
$N$ $K$ $A_1$ $A_2$ $\dots$ $A_N$
Output
Print the answer as an integer.
Sample Input 1
5 2 3 1 5 4 9
Sample Output 1
2
Consider removing exactly two elements from $A=(3,1,5,4,9)$.
- For example, if you remove the 2nd element $1$ and the 5th element $9$, the resulting sequence is $B=(3,5,4)$.
- In this case, the maximum value of $B$ is $5$ and the minimum value is $3$, so (maximum value of $B$) $-$ (minimum value of $B$) $=2$, which is the minimum possible value.
Sample Input 2
6 5 1 1 1 1 1 1
Sample Output 2
0
Sample Input 3
8 3 31 43 26 6 18 36 22 13
Sample Output 3
18
Output
分数：250分
问题陈述
给你一个长度为N的序列A。
从A中自由选择恰好K个元素并删除它们，然后将剩余的元素按原顺序连接起来形成一个新的序列B。
找出可能的最小值：B的最大值减去B的最小值。
约束条件
- 所有输入都是整数。
- $1 \le K < N \le 2 \times 10^5$
- $1 \le A_i \le 10^9$
输入
输入从标准输入以以下格式给出：
$N$ $K$ $A_1$ $A_2$ $\dots$ $A_N$
输出
以整数形式打印答案。
示例输入1
5 2 3 1 5 4 9
示例输出1
2
考虑从$A=(3,1,5,4,9)$中删除恰好两个元素。
- 例如，如果你删除第2个元素$1$和第5个元素$9$，得到的序列是$B=(3,5,4)$。
- 在这种情况下，B的最大值是$5$，最小值是$3$，所以（B的最大值）-$（B的最小值）=2，这是可能的最小值。
示例输入2
6 5 1 1 1 1 1 1
示例输出2
0
示例输入3
8 3 31 43 26 6 18 36 22 13
示例输出3
18