用的优先队列,但2个tle,能优化吗

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

Tachikawa_Ruri @ 2023-02-12 22:19:53


# include<bits/stdc++.h>
using namespace std;
int n,k;
priority_queue<int>a;
inline void read(int &x)
{
    char ch=getchar();x=0;
    for(;ch<'0'||ch>'9';ch=getchar());
    for(;ch>='0'&&ch<='9';ch=getchar()) x=x*10+ch-'0';
}
int main()
{
    int l;
    read(n),read(k);
    for(int i=1;i<=n;i++)
    {
        read(l);
        if(i<=k+1)
        {
            a.push(l);
        }
        else if(a.top()>l)
        {
            a.pop();
            a.push(l);
        }
    }
    printf("%d",a.top());
}

by bamboo12345 @ 2023-02-12 22:22:47

@Tachikawa_Ruri 显然,这题让你O(n)


by ncwzdlsd @ 2023-02-12 23:49:58

@Tachikawa_Ruri 显然,STL 时间复杂度不占优势,因为优先队列的时间复杂度为 O(n\log n),但是这道题让您跑 O(n)

验证码 24nb 祭


|