A1916 | $求第 k 小的数$

时间限制3s

内存限制256MB

通过 / 提交0/0

题目描述

输入 $n$（$1 \le n < 5000000$ 且 $n$ 为奇数）个数字 $a_i$（$1 \le a_i < {10}^9$），输出这些数字的第 $k$ 小的数。最小的数是第 $0$ 小。 请尽量不要使用 nth_element 来写本题，因为本题的重点在于练习分治算法。

输入的第一行包含两个整数 n 和 k，其中 n 是数组的长度（$1 \leq n < 5,000,000 且 n 为奇数$），$k$ 是要找的第 $k$ 小的数的位置（最小的数是第 0 小）。 第二行包含 $n$ 个整数，表示数组的元素，每个元素满足 $1 \leq a_i < 10^9$。

输出一个整数，表示数组中第 k 小的数。

输入 #1

5 1
4 3 2 1 5

输出 #1

C++ 编辑器

输入

输出