思路
基本上就是快排的一种小的变形
代码
#include<iostream>
#include<algorithm>
using namespace std;
const int maxn = 1e5+7;
int n, k, a[maxn];
int solve(int left, int right, int p){
if(left >= right) return a[left];
int lt = left -1, rt = right + 1;
int mid = a[lt + rt >> 1];
while(lt < rt){
do lt++; while(a[lt] < mid);
do rt--; while(a[rt] > mid);
if(lt < rt)
swap(a[lt], a[rt]);
}
if(left + p-1 <= rt)
solve(left, rt, p);
else
solve(rt+1, right, p-(rt-left+1));
}
int main(){
scanf("%d%d", &n, &k);
for(int i=0; i<n; i++)
scanf("%d", &a[i]);
printf("%d\n", solve(0, n-1, k));
}