本题 正确的桶排序方法
第k小数
https://ac.nowcoder.com/acm/problem/207028
他说了数字的范围是 int 以内, 所以直接桶排序会爆内存（也不知道为什么能过, 出题人数据太水）
正确同排序方法 应该是先缩小范围, 然后在桶
先采用分块的方式 开个vector <int> [maxn] 来放
然后 On 的时间就可以把范围缩小其中的某个 块内
这个时候最大值和最小值相差不超过 1e5， 采用桶排序即可
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <vector>
#include <queue>
#include <map>
#include <bitset>
#define rep(i, a, b) for (int i = (a); i <= (b); ++i)
#define per(i, a, b) for (int i = (a); i >= (b); --i)
#define mk make_pair
#define fi first
#define se second
#define pii pair <int, int>
#define NEXT(i, a) for (int i = head[a]; i; i = edge[i].nex)
#define space putchar(' ')
#define enter putchar('\n')
#define imit(t) '[' << #t << ": " << (t) << ']'
using namespace std;
typedef long long ll;
template <class T>
void read(T& x) {
char c; bool op = false;
while (c = getchar(), c < '0' || c > '9')
if (c == '-') op = true;
x = c - '0';
while (c = getchar(), c >= '0' && c <= '9')
x = (x << 1) + (x << 3) + c - '0';
if (op) x = -x;
}
template <class T>
void write(T x) {
if (x < 0) putchar('-'), x = -x;
if (x >= 10) write(x / 10);
putchar('0' + x % 10);
}
const int MAXN = 5e6 + 5;
const int maxn = 1e5 + 5;
vector <int> v[maxn];// 记录每一块的元素
int k, max_; // 表示每一块的厚度 以及最大值
inline int get(int x) { // 返回x 所在的快
return x / k;
}
int a[MAXN]; // 记录每个元素
int n, m;
int Hash[maxn];// 同排序用的桶
int main() {
int t; read(t);
while (t--) {
read(n), read(m);
max_ = 0;
rep(i, 1, n) read(a[i]), max_ = max(max_, a[i]);
k = sqrt(max_) + 1;
rep(i, 0, k) v[i].clear(), Hash[i] = 0;
rep(i, 1, n) v[get(a[i])].push_back(a[i]);
int j = -1;
rep(i, 0, k) {
if (v[i].empty()) continue;
if ((m - (int)v[i].size()) <= 0) {
j = i;
break;
}
m -= v[i].size();
}
rep(i, 0, v[j].size() - 1) Hash[v[j][i] - j * k]++;
rep(i, 0, k) {
if (m - Hash[i] <= 0) {
write(i + j * k), enter; break;
}
m -= Hash[i];
}
}
return 0;
}
