Skip to content

1300: k-th Smallest Number

题目

题目描述

给定 $n$ 个正整数,请找出其中的第 $k$ 小的数。

输入可能有重复数字,此时第 $k$ 小的值定义为唯一的 $x$,满足 $$ (\left|\{y | y < x\}\right| < k) \land (\left|\{y | y \geq x\}\right| \geq n - k), $$ 也即将整个序列从小到大排序后的第 $k$ 个数。

Input

由于输入可能很大,本题采用奇怪的方式读入。你可以直接使用这段代码完成读入。

请注意,输入存储在 $a[1\dots n]$ 里,$0$ 不存内容。

其中,$1 \leq k \leq n \leq 4\times 10 ^ 7, 0 \leq a_i < 2^{31}$。

cpp const int N = 4e7 + 1; int n, k; int a[N]; void read_input_data() { int m; cin >> n >> k >> m; for (int i = 1; i <= m; i++) { cin >> a[i]; } unsigned int z = a[m]; for (int i = m + 1; i <= n; i++) { z ^= z << 13; z ^= z >> 17; z ^= z << 5; a[i] = z & 0x7fffffff; } }

Output

请输出到 stdout 中。

输出一行,包含一个整数,为你的答案。

Sample Input

txt 3 3 3 2 3 3

txt 5 4 1 1919810

Sample Output

txt 3

txt 737192472

Constraints

Time Limit: 1s

Memory Limit: 512MB

Note

第二组样例实际上代表的数是 $[1919810, 132030712, 737192472, 1757748577, 642384501]$。

输入格式解释:

输入第一行,三个正整数。输入第二行 $m$ 个空格隔开的整数,表示 $a_1, \dots , a_m$。

$a_{m+1},\dots, a_n$ 使用 xorshift 随机生成器生成, $$ \begin{align} a_{m + i} &= z_i \bmod 2 ^ {31}, \end{align} $$ 其中, $$ z_0 = a_m $$ $$ x_i = z_{i - 1} \oplus (z_{i -1} \times 2 ^ {13}) (\bmod 2 ^ {32}) $$ $$ y_i = x_i \oplus \left \lfloor \frac {x_i} {2 ^ {17}}\right \rfloor (\bmod 2 ^ {32})$$ $$ z_i = y_{i - 1} \oplus (y_{i -1} \times 2 ^ {5}) (\bmod 2 ^ {32}) $$ $\oplus$ 表示异或操作。 我对于因为这个 OJ 只支持单行公式而看起来没有对齐,深表遗憾。

Oops! 本题目还没有解答!

助教老师们编题的速度,已经超过了解题的速度!

OJ翻了一新,但本解答集还大多用的是2017-2019级,甚至更早的同学们贡献的答案。

如果你已经AC了,可以的话,请您参考添加页面,与大家一起分享你的题解!