最后两个点T了

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

Citrusn @ 2022-08-13 14:51:43

#include <iostream>
#include <iomanip>
using namespace std;
const int N=5e6+5;
int a[N],n,k;
void QS(int l,int r)
{
    int b=a[(l+r)>>1],ll=l,rr=r;
    while(ll<=rr)
    {
        while(a[ll]<b) ++ll;
        while(a[rr]>b) --rr;
        if(ll<=rr) swap(a[ll++],a[rr--]);
    }
    if(l<rr) QS(l,rr);
    if(r>ll) QS(ll,r);
}
int main()
{
    cin>>n>>k;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
    }
    QS(1,n);
    cout<<a[k+1]<<" ";
    return 0;
}

by OldVagrant @ 2022-08-13 14:55:23

这不是让你快排过的题,请使用时间复杂度 O(n) 的算法
当然你要是用基数排序啥的那也行


by Citrusn @ 2022-08-13 16:35:02

@z_z_y 已过,加了个快读然后O2,就过了


by OrangeRainee @ 2022-08-14 08:33:49

不知道怎么T的


|