USACO 3.1 Humble Numbers丑数_优先队列

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


<![CDATA[

<

div class="markdown_views">

题目大意

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

思路

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

#include <stdio.h>
#include <queue>
using namespace std;
priority_queue<long long,vector<long long>,greater<long long> > 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]<x)
        {
            t++;
            f[t]=x;
        }
        heap.pop();
        for (int j=1;j<=m;j++)
            heap.push(x*a[j]);
    }
    printf("%I64d\n",f[n+1]);
}