2020年牛客算法入门课练习赛1 A题题解

#include<iostream>
#include<algorithm>
using namespace std;
const int maxn=5000005;
int a[maxn];
void quickSelect(int a[],int l,int r,int rank)
{
    int i=l,j=r,mid=a[(l+r)>>1];
    do{
        while(a[i]<mid) ++i;
        while(a[j]>mid) --j;
        if(i<=j){
            swap(a[i],a[j]);
            ++i;
            --j;
        }
    }while(i<=j);
    if(l<=j && rank<=j-l+1) quickSelect(a,l,j,rank);
    if(i<=r && rank>=i-l+1) quickSelect(a,i,r,rank-(i-l));
}
int quick_select(int a[],int n,int k)//第k小
{
    quickSelect(a,1,n,k);
    return a[k];
}
inline int read(){
    int x = 0, f = 1;
    char ch = getchar();
    while(ch < '0' || ch > '9'){
        if (ch == '-')
            f = -1;
        ch = getchar();
    }
    while(ch >= '0' && ch <= '9'){
        x = (x<<1) + (x<<3) + (ch^48);
        ch = getchar();
    }
    return x * f;
}
int main()
{
    int t;
    t=read();
    while(t--)
    {
        int n,k;
        cin>>n>>k;
        for(int i=0;i<n;i++)
            a[i]=read();

        cout<<quick_select(a,n,k)<<endl;
    }
    return 0;
}

这里使用简单sort会直接tle，所以这里采用了分治快排思想求解第k小数