← 返回题目列表

AtCoder · abc361_c

E. 让它们变窄

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

分数: 250 点

问题陈述

给你一个序列 A 长度 N.
自由选择准确 K 元素来自 A 并删除它们,然后按原始顺序连接剩余元素以形成新序列 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).

  • 例如,如果删除第二个元素 1 和第 5 个元素 9,结果序列是 B=(3,5,4).
    • 在这种情况下,最大值 B is 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