USACO 3.1 Humble Numbers丑数_优先队列

发布于 2019-04-21  6 次阅读


题目大意

找出自然数中因子含有a[i]的第m小的数

思路

用优先队列直接求解,每次往堆里面塞topa[1],topa[2]……然后删掉堆顶,但会蜜汁爆内存。。。
时间复杂度很玄学,不会算。。。
大神指点
O(NKlogN)

#include 
#include 
using namespace std;
priority_queue,greater > heap;
long long a[10000],f[10000];
int main()
{
    long long m,n;
    scanf("%I64d%I64d",&m,&n);
    for (int i=1;i<=m;i++)
    {
        scanf("%I64d",&a[i]);
    }

    heap.push(1);
    long long t=0;
    while (t<=n)
    {
        int x=heap.top();
        if (f[t]
]]>