P4792 - 【深基9.例4】求第 k 小的数

文件提交：无需freopen 内存限制：250 MB 时间限制：1.000 S

评测方式：普通裁判

金币值：

命题人：

提交：0 解决：0

# 【深基9.例4】求第 k 小的数

题目描述

输入 $n$ 个数字 $a_i$，输出这些数字中第 $k$ 小的数。最小的数是第 $0$ 小。请尽量不要使用 `nth_element` 来写本题，因为本题的重点在于练习分治算法。

第一行有两个整数，分别表示 $n$ 和 $k$。第二行有 $n$ 个整数，第 $i$ 个数表示 $a_i$。

一个整数，表示第 $k$ 小的数。

5 1
4 3 2 1 5

对于 $100\%$ 的数据，$1\le a_i \lt {10}^9$，$1 \le n \lt 5\times 10^6$，且 $n$ 为奇数。标签: P1923|分治

P1923|【深基9.例4】求第 k 小的数