第四个点MLE何解,求带师指点

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

Play_CP_4fun @ 2022-05-06 00:52:51

#include <bits/stdc++.h>
using namespace std;
const int N = 5e6 + 10;
int n, ans, k, a[N];
void quick_sort(int a[], int l, int r) {
    if (l >= r) {
        ans = a[l];
        return;
    }

    int i = l, j = r, pivot = a[(l + r) / 2];
    while (i < j) {
        while (a[i] < pivot) i++;
        while (a[j] > pivot) j--;
        if (i < j) {
            swap(a[i], a[j]);
            i++;
            j--;
        }
    }

    if (k <= j) quick_sort(a, l, j);
    else if (k >= i) quick_sort(a, i, r);
    else quick_sort(a, j + 1, i - 1);
}
int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    cin >> n >> k;
    for (int i = 0; i < n; i++) cin >> a[i];
    quick_sort(a, 0, n - 1);
    cout << ans;
    return 0;
}

RT


by Laffey @ 2022-05-06 08:04:24

是直接敲了个快排吗?这道题正解应该不是排序。再想想?


by Play_CP_4fun @ 2022-05-06 11:16:27

@Laffey 没啊,快排里面加判断了啊, a了1235,就第四个点MLE


|