40分求解
查看原帖
40分求解
618216
TompkinsAlex楼主2024/8/1 01:12
#include <bits/stdc++.h>
using namespace std;
const int maxn =5000010 ;
int n,k,q[maxn];

int kth_num(int q[],int l , int r ,int k){
    if(l==r) return q[l];
    int i= l-1,j=r+1,x=q[(l+r)/2];
    while(i<j){
        while(q[++i]<x);
        while(q[--j]>x);
        if(i<j) swap(q[i],q[j]);
    }
    int left_cnt = j-l+1;
    if(k<=left_cnt) return kth_num(q,l,j,k);
    return kth_num(q,j+1,r,k-left_cnt);
}
int main(){
    scanf("%d%d",&n,&k);
    for(int i = 0;i<n;i++)    
    scanf("%d",&q[i]);
    printf("%d",kth_num(q,0,n-1,k));
    return 0;
}
2024/8/1 01:12
加载中...