2292. 录取分数线
1000ms
256MB
简单
排序
题目描述
新学年,学校将成立信息学兴趣小组提高班。由于指导教师精力有限,只能选拔部分学生参加。
选拔规则如下:
1. 计划从 $N$ 个参加选拔的学生中,按照成绩从高到低的顺序,录取不超过 $M$ 个成员。
2. 录取的成员要尽可能地多,但不得超过 $M$ 个(含 $M$ 个)。
3. **公平性原则**:如果划定的分数线为 $X$,那么所有分数 $\ge X$ 的学生都必须被录取。如果将分数线降到某个并列的分数会使得总录取人数超过 $M$,则必须放弃该分数段的所有学生,可能导致最终实际录取的人数达不到计划数 $M$。
请你编程划定录取分数线,分数线为最后一名被录取的学生的分数。
输入格式
- 第一行包含两个正整数 $N$ 和 $M$ ($2 \le M \le N \le 2 \times 10^5$),分别表示报名人数和计划录取人数。
- 接下来 $N$ 行,每行包含一个整数,表示一个学生的考试成绩(成绩 $\le 10^9$)。
- 数据保证相同成绩的学生数量不超过 $M$。
输出格式
- 输出只有 1 行,为录取分数线。
样例 1
输入 (Input)
5 3 90 75 80 80 95
输出 (Output)
90
- 对于所有数据:$2 \le M \le N \le 2 \times 10^5$,成绩 $\le 10^9$。
- **样例解释**:
将成绩从高到低排序后为:$95, 90, 80, 80, 75$。
- 如果录取前 3 名($95, 90, 80$),由于存在两个并列的 $80$ 分,为了公平必须同时录取,这会导致录取人数达到 4 人,超过了 $M=3$。
- 因此只能退而求其次,录取前 2 名($95, 90$),此时最后一名录取的学生分数为 $90$。
› 输入 stdin
CtrlShiftEnter
‹ 输出 stdout
错误 stderr
操作成功