先上传送门

其实这题大可不必用快读O(nlogn)的算法，因为夹杂了太多的重复计算

我们只需要将小于该元素的放在左边，大于他的放在右边即可

因此引入快速选择算法，该算法可求第k大（小）元素，这里介绍第k大，其实也等价与求第n-k+1小

算法流程大致如下：

随机选择一个数，将他与最后一个元素交换（随机是因为该算法平均为O(n)，但如果对于一个排好序的数组最坏会O(n²)，与快排是一样的道理，所以随机选择可以最大化保证复杂度，不理解没关系，往下看）

定义两个指针i,j，初始时均在队首

接下来循环遍历直至指针j到达队尾

重复如下操作：

比较指针j所指元素与队尾元素大小，

　　若a_j <= a_end 则交换i,j指针元素，即a_i,a_j 同时将i , j 分别右移到下一元素

　　否则 右移j指针至下一元素

结束后(此时j即为队尾) 交换a_i a_j

到了这里，a_i右边都是比他大的，左边都是比他小的

此时如果i 恰好为第end-k位，则结束，返回

否则视情况递归执行左右区间

最终得到所求第k大数

此题得解

#include<cstdio>
#include<algorithm>
#include<queue>
#include<iostream>
#include<cstring>
#include<string>
#include<ctime>
#include<cstdlib>
using namespace std;
int a[5000005],n,kk;
int quickselect(int l,int r,int k){
    int p = rand() % (r - l + 1) + l;
    swap(a[p],a[r]); 
    int i = l,j = l;
    while(j < r){
        if(a[j] <= a[r])swap(a[i++],a[j]);
        j++;
    }
    swap(a[i],a[j]);
    if(r == k + i - 1)return a[i];
    if(r > k + i -1)return quickselect(i+1,r,k);
    else return quickselect(l,i - 1,k - (r - i + 1));
}
int main(){
    srand(time(NULL));
    scanf("%d%d",&n,&kk);
    for(int i=1;i<=n;++i)scanf("%d",a+i);
    printf("%d",quickselect(1,n,n-kk));//题里最小是第0小
}