60分求助

P1923 【深基9.例4】求第 k 小的数

轩酱自带逆风 @ 2022-07-21 11:25:59

#include<bits/stdc++.h>
using namespace std;
const int N=5000005;
int q[N],n,k;
void quick_sort(int q[],int l,int r){
    if(l>=r)return ;
    int x=q[(l+r)/2],i=l-1,j=r+1;
    while(i<j){
        do i++;while(q[i]<x);
        do j--;while(q[j]>x);
        if(i<j)swap(q[i],q[j]);
    }
    quick_sort(q,l,j);
    quick_sort(q,j+1,r);
}
int main(){
    scanf("%d%d",&n,&k);
    for(int i=0;i<n;i++)scanf("%d",&q[i]);
    quick_sort(q,0,n-1);
    printf("%d",q[k]);
    return 0;
}

by BugGod @ 2022-07-21 11:51:21

不需要这么麻烦,只要std::sort+吸氧就行了


by BugGod @ 2022-07-21 11:54:06

直接快排不太行,O(n\log n)的复杂度最大4000000,5000000(大概)会TLE


by BugGod @ 2022-07-21 11:59:51

我们可以借助快排的分治思想,在每次将数列分成三部分后处理。


by BugGod @ 2022-07-21 12:07:03

只要确定区间就在区间里搜索,不需要考虑别的地方,以此优化。

另外,既然出题人温馨提示,我们也可以用STL(标准模板库)中的

nth_element函数

用法如下:

nth_element(x,x+k,x+n)

输出a_k即可。

虽然STL普遍常数大,但是本题这么水的数据还是可以过的。


by 轩酱自带逆风 @ 2022-08-11 09:59:33

@luoyida 感谢


|