分数: 300 分
问题陈述
高桥负责学校的设施管理。学校有 N 教室,以及每个教室 i (1 \leq i \leq N)安装了一台旧空调。每个教室的空调都有劣化等级 D_i,其中老化程度越高意味着空调越旧并且性能越差。
这一次, M 新空调已到货。高桥可以选择 0 或更多以及 M 或更少的不同教室 N 教室,并将每个选定教室的旧空调更换为一台新空调。每个教室最多可更换一次,无需全部使用 M 新空调。更换后的教室的恶化程度变为 0,而未进行更换的教室的恶化程度仍保持其原始值 D_i.
高桥希望明智地选择更换教室,以尽量减少更换后所有教室的最大恶化程度。找出该最大值的最小可实现值。
约束
- 1 \leq N \leq 2 \times 10^5
- 1 \leq M \leq N
- 0 \leq D_i \leq 10^9
- 所有输入值均为整数
输入
N M D_1 D_2 \ldots D_N
- 第一行包含一个整数 N 代表教室数量和一个整数 M 代表到达的新空调数量,以空格分隔。
- 第二行包含整数 D_1, D_2, \ldots, D_N 代表每个教室的恶化程度,以空格分隔。
输出
在一行中打印更换后所有教室的最大恶化程度的最小可达到值。
示例输入 1
5 2 3 1 4 1 5
示例输出 1
3
示例输入 2
7 7 10 20 30 40 50 60 70
示例输出 2
0
示例输入 3
10 3 100 200 300 400 500 600 700 800 900 1000000000
示例输出 3
700