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了，可以的话，请您参考添加页面，与大家一起分享你的题解！