大佬帮忙看看为什么不行

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

Zzy20060323 @ 2024-09-21 00:13:56

#include<stdio.h>
#include<time.h>
#include<stdlib.h>
int n, k;
int a[5000001], b[5000001], c[5000001], d[5000001];
void px(int s, int l)
{
    if (s >= l)
    {
        return;
    }
    int mid = rand() % (l - s) + s;
    int tb = 0, tc = 0, td = 0;
    for (int i = s; i < l; i++)
    {
        if (a[i] < a[mid])
        {
            b[++tb] = a[i];
        }
        else if (a[i] > a[mid])
        {
            c[++tc] = a[i];
        }
        else
        {
            d[++td] = a[i];
        }
    }
    for (int i = 1; i <= tb; i++)
    {
        a[s + i - 1] = b[i];
    }
    for (int i = 1; i <= td; i++)
    {
        a[s + tb + i - 1] = d[i];
    }
    for (int i = 1; i <= tc; i++)
    {
        a[s + tb +td + i - 1] = c[i];
    }
    px(s, tb+s);
    px(tb + td + s, l);
}
int main()
{
    srand((unsigned int)time(0));
    scanf("%d%d", &n, &k);
    for (int i = 0; i < n; i++)
    {
        scanf("%d", &a[i]);
    }
    px(0, n);
    printf("%d", a[k]);
    return;
}

by lizechenQAQ @ 2024-09-21 05:35:40

@Zzy20060323 sort是个好东西


by Zzy20060323 @ 2024-09-21 07:35:33

大佬能告诉我这为什么不行吗


by __owowow__ @ 2024-09-21 08:03:26

@Zzy20060323 其实快排代码更短,还更快。建议这道题用快排


by __owowow__ @ 2024-09-21 08:04:37

@Zzy20060323 而且这道题 nlogn过不了的


|