AcWing 786. 第k个数
原题链接
简单
作者:
l.G.r
,
2024-03-25 22:44:15
,
所有人可见
,
阅读 1
# include <iostream>
using namespace std;
const int N = 100008;
int q[N];
void return_k(int* q, int l, int r, int k) {
bool is_sorted = true;
for (int i = l + 1; i <= r; i ++) {
if (i == l) continue;
if (q[i] > q[i - 1]) continue;
is_sorted = false;
break;
}
if (is_sorted) return;
int x = q[(l + r) >> 1];
q[(l + r) >> 1] = q[r];
int head = l;
int tail = r;
while (l < r) {
while (l < r && q[l] <= x) l ++;
q[r] = q[l];
while (l < r && q[r] >= x) r --;
q[l] = q[r];
}
q[l] = x;
if (l == k - 1) return;
if (k < l) return_k(q, head, l - 1, k);
else return_k(q, l + 1, tail, k);
}
int main(){
int n, k;
scanf("%d%d", &n, &k);
for (int i = 0; i < n; i ++) scanf("%d", &q[i]);
return_k(q, 0, n - 1, k);
cout << q[k - 1] << endl;
}