C语言60分 二分法 后俩个RE 求帮助谢谢!

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

a1760084203 @ 2023-04-15 12:20:26

#include <stdio.h>
int Partition(int* a, int left, int right)
{
    int pivot = a[left];
    while (left < right)
    {
        while (left < right && a[right] > pivot)
            right--;
        a[left] = a[right];
        while (left < right && a[left] <= pivot)
            left++;
        a[right] = a[left];
    }
    a[left] = pivot;
    return left;
}
void quick(int* a, int left, int right)
{
    int stack[1000000], top = -1;
    stack[++top] = left;
    stack[++top] = right;
    while (top >= 0)
    {
        right = stack[top--];
        left = stack[top--];
        int pivot = Partition(a, left, right);
        if (pivot - 1 > left)
        {
            stack[++top] = left;
            stack[++top] = pivot - 1;
        }
        if (pivot + 1 < right)
        {
            stack[++top] = pivot + 1;
            stack[++top] = right;
        }
    }
}
int main()
{
    int N,M, a[100000];
    scanf("%d %d", &N,&M);
    for (int i = 0; i < N; i++)
    {
        scanf("%d", &a[i]);
    }
    quick(a, 0, N - 1);

        printf("%d ", a[M]);

    return 0;
}

by CQ天神 @ 2023-04-15 12:31:45

@a1760084203 建议看https://www.luogu.com.cn/blog/Dimly/solution-p1923喵


by chenmingwang @ 2023-04-15 13:16:09

用scanf和printf加个O2试试


by a1760084203 @ 2023-04-15 20:45:27

@yr317430_xht 分成三组确实没有想过,谢谢了


by a1760084203 @ 2023-04-15 20:45:51

@chenmingwang em...不懂什么意思


|