60分 RE了

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

XHWxhw123 @ 2023-05-09 20:30:16

#include<bits/stdc++.h>
#define MAXN 500010
using namespace std;

int x,y,tmp,a[MAXN],n,k;
bool flag=0;

int qspx(int l,int r)
{
    int mid=(l+r)/2;
    tmp=a[mid];
    x=l;y=r;
    if(flag)
        return 0;
    do
    {
        while(a[x]<tmp)
            x++;
        while(a[y]>tmp)
            y--;
        if(x<=y)
        {
            int r=a[x];
            a[x]=a[y];
            a[y]=r;
            x++;y--;
        }
    }
    while(x<=y);
    if(k<=y)
        qspx(l,y);
    else if(x<=k)
        qspx(x,r);
    else
    {
        cout<<a[y+1];
        flag=1;
        return 0;
    }
    return 0;
}

int main()
{
    cin>>n>>k;
    k++;
    for(int i=1;i<=n;i++)
        cin>>a[i];
    qspx(1,n);
    return 0;
}

by wuyin331 @ 2023-05-09 20:36:35

@XHWxhw123 数组开小了。


by XHWxhw123 @ 2023-05-09 20:43:06

多过了一个点,最后一个点又TLE了


by XHWxhw123 @ 2023-05-09 20:43:54

@wuyin331


by XHWxhw123 @ 2023-05-09 21:02:51

写快读AC了


|