新人求助!40分/60分,整一晚上了

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

HLlll @ 2022-01-29 02:49:50

#include <cstdio>
#include <iostream>
#include <cstring>

using namespace std;
long long a[5000010];
inline int read()
{ //快速读入
    int x = 0, f = 1;
    char c = getchar();
    while (c < '0' || c > '9')
    {
        if (c == '-')
            f = -1;
        c = getchar();
    }
    while (c >= '0' && c <= '9')
    {
        x = (x << 1) + (x << 3) + (c ^ 48);
        c = getchar();
    }
    return x * f;
}
void qsort(int begin, int end, int k)
{
    int left = begin;
    int right = end;
    int mid = a[(begin + end) / 2];
    if (begin >= end)
        return;
    while (left < right)
    {
        while (a[right] >= mid && left < right)
            right--;
        while (a[left] <= mid && left < right)
            left++;
        swap(a[left], a[right]);
    }
    a[left] = mid;
    if (k - 1 < left)
        qsort(begin, left - 1, k);
    else if (k - 1 > left)
        qsort(left + 1, end, k);
    else
        return;
}
int main()
{
    int n, k;
    //cin>>n>>k;
    scanf("%d%d", &n, &k);
    for (int i = 0; i < n; i++)
    {
        scanf("%d", &a[i]);
    }
    qsort(0, n - 1, k);
    printf("%d", a[k]);
    return 0;
}

第33行和34行,如果没有等号就只能过后面三个测试(前两个TLE),如果有等号就只能过前面两个测试(后面三个WA),这是为什么啊,求大佬解答


by strcmp @ 2022-01-29 09:55:41

@HLlll 1.一般两种方法:小根堆O(klogn),分治O(n)

2.这道题是在于练习分治算法,任何排序都是投机取巧的,你真想A这道题就用基数排序。但不建议,最好去学一下正解。

分治和小根堆请自己去BDFS。


by strcmp @ 2022-01-29 09:57:17

@wql463 小根堆容易被卡成O(nlogn),最好去学一下分治方法。


by yeanna @ 2022-08-10 18:39:07

@wql463 请问怎么看出来的10^8很悬,怎么看出来的是0(n)的题


by LCATreap @ 2022-08-10 22:22:21

@yeanna 一般默认评测姬速度是每秒 10^8 个运算,实际情况下可能会更快,但综合考虑常数之后差不多是速度上限了。

一般用数据范围判断时间复杂度

n \le 11 \to \mathrm O(n!) n \le 20 \to \mathrm O(2^n) n \le 5 \times 10^3 \to \mathrm O(n^2) n \le 10^5 \to \mathrm O(n \sqrt n),\,\mathrm O(n \log n),\,\mathrm O(n \log^2 n) n \le 10^6 \to \mathrm O(n \log n) n \le 10^7 \to \mathrm O(n) n \le 2^{10000000} \to \mathrm{O(\log n)} n \ge 2^{100000000} \to \mathrm{O(1)}

by yeanna @ 2022-08-11 10:50:43

@wqlGZZC 感谢!


上一页 |