竟然没人用 $nth\_element$ ，那就那 $nth\_element$ 来水一发

浅谈一下 $nth\_element$ ，这是一个 $STL$ 库中自带的神奇函数，它的原理就是快速查找，能快速找出第 $k$ 大的数。

用法如下：

$nth\_element(数组名，数组名+第k小元素,数组名+元素个数)$

运用此函数时间复杂度为 $O(n)$ ，但是 $STL$ 的常数普遍较大，不过还是能通过此题的。

$AC~Code$

#include <cstdio>
#include <algorithm>
#define ll long long
using namespace std;
const int MAXN = 5e6 + 5;
ll n, k, a[MAXN];
int main()
{
    scanf("%lld%lld", &n, &k);
    for (int i = 0; i < n; i++)
        scanf("%lld", &a[i]);
    nth_element(a, a + k, a + n);
    printf("%lld\n", a[k]);
    return 0;
}

这题属于是快排经典题了，数据范围5e6，暴力sort的话会超时，所以只能用快排，平均时间复杂度$O(n)$ 。

唯一需要注意的是题目中说“最小的数是第0小”，坑了我老半天😕

部分代码：

ll qsort(ll L,ll R,ll k){
    if(L==R)
        return a[L];
    swap(a[L],a[L+rand()%(R-L+1)]);
    ll x=a[L],l=L,r=R,index=L;
    while(l<r){
        while(l<r&&a[r]>x)
            r--;
        if(l<r)
            a[index]=a[r],index=r,l++;
        while(l<r&&a[l]<x)
            l++;
        if(l<r)
            a[index]=a[l],index=l,r--;
    }
    if(l-L>=k)
        return qsort(L,l-1,k);
    else if(l-L==k-1)
        return x;
    else
        return qsort(l+1,R,k-(l-L+1));
}
主函数中：
    srand(time(0)); // 以时间戳为随机种子
    printf("%lld",qsort(1,n,k+1)); // 因为最小是第0小，所以这里一定要k+1