AcWing 786. 第k个数
原题链接
简单
作者:
Value
,
2020-04-25 09:30:37
,
所有人可见
,
阅读 503
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
const int N = 100010;
int a[N];
int n, m;
int quick_sort(int q[], int l, int r){
if(l == r) return q[l];
int aim = q[(l + r) / 2];
int i = l - 1, j = r + 1;
while(i < j){
do i ++ ; while(a[i] < aim);
do j -- ; while(a[j] > aim);
if(i < j) swap(a[i], a[j]);
}
if(j+1 >= m) return quick_sort(q, l, j);
else return quick_sort(q, j + 1, r);
}
int main(){
cin >> n >> m;
for(int i = 0; i < n; i ++ ) scanf("%d", &a[i]);
cout << quick_sort(a, 0, n-1);
return 0;
}