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

cengzh · 2025-01-03 12:58:19 · 题解

切水题ing，好的这里是传送门。

突然来做这题的原因是机房同学不知为何发现这题然后自信打上 sort 然后爆两个点发现蜜汁数据 5000000 于是在大家开始头脑风暴讨论该题解法结果一群考 NOIP 的人硬是没憋出来 O(n) 正解于是本人憋出了 O(n \log k) 神奇解法。

其实不用看上面的。分割线~~~

#

看到这题苦思冥想半天，虽然拼尽全力无法得出 O(n) 正解，但是突然想到可以有数据结构上的优化。没错就是堆。

堆的用法不必多说，我们希望最后 O(1) 输出答案，那么我们开一个大根堆，最终堆中的数为第 0 小到第 k 小的数，堆顶即为我们所求的答案。

算法流程：取前 k 个数入堆，然后从第 k+1 个数向后遍历，如果当前第 i 个数小于堆顶的数，那么堆顶一定不是第 k 小的数，因为还有比它更小的。我们弹出堆顶，插入当前数，此时堆顶就表示 [1,i] 中第 k 小数。

使用堆的时间复杂度会比线段树、快速排序的小一些。因为在数据随机的情况下有些数不会进堆，即使遇到极端数据如单调下降数列，我们也可以通过在一开始时随机插入 k 个数入堆或者判断 k 与 n 的关系，决定找顺序第 k 小还是逆序第 k 小来降低复杂度。

当然本题不需要，但这个思想还蛮好的？

以下为代码，堆用 STL 优先队列代替。

# include <iostream>
# include <queue> 

using namespace std;

int a[5000005];
bool check[5000005];
priority_queue<int,vector<int>,less<int> > q;

int main (void)
{
    int n,k;
    scanf ("%d %d",&n,&k);
    k++;
    for (int i=1;i<=n;i++)
    {
        scanf ("%d",&a[i]);
    }

    for (int i=1;i<=n;i++)
    {
        if (q.size() < k)
        {
            q.push(a[i]);
        }
        else if (a[i] < q.top())
        {
            q.pop();
            q.push(a[i]);
        }
    }

    printf ("%d",q.top());

    return 0;
}