入门OJ 1126【丑数】

描述

对于一给定的素数集合 S = {p1, p2, ..., pK},如果一个数字，当我们对其做完质因子分解后，其质因子全是来自我们给定的素数集合，则认为这个数字是个丑数。
注意：我们不认为1 是一个丑数。 
你的工作是对于输入的集合S去寻找第N个丑数。

输入输出格式

输入

第 1 行: 二个被空间分开的整数:K 和 N ， 1<= K<=100 ， 1<= N<=100,000. 
第 2 行: K 个被空间分开的整数:集合S的元素

输出

第N个丑数。.

输入输出样例

输入样例

4 19
2 3 5 7

输出样例

27

解题思路

　　首先想到的就是一个一个慢慢计算上去，但是肯定会超时，果断放弃，然后用了队列，每次取出队头，然后一个一个乘集合里的数，但是发现这个没按大小顺序排列，所以又WA了。然后，一种很神奇的东西——优先队列出现了：

　　优先队列是经过一系列玄学的操作，让优先级高的先出列

　　priority_queue<int> q;通过操作，按照元素从大到小的顺序出队

　　priority_queue<int,vector<int>, greater<int> > q;通过操作，按照元素从小到大的顺序出队

　　本题果断选第二种。注意，这里不再用q.front()而是用q.top()取队首元素。

　　然后呢，你就会发现，2*3和3*2重复了，这可怎么办呢？打标记吗？但是我嫌太麻烦，聪明的我果断选择了另一种方式：

　　那么我们推一推可能会发现，我们让每一个取出的元素乘质数时从小到大，如果取出的元素%这个质数=0，那么就乘完这个质数就不继续向后乘了（因为某个质数的k次方也是丑数，所以要放进去）。每一个存进去的数字，都是从小到大乘过来的，就可以避免重复，于是可以优化一个logn的复杂度。最后在循环到第n次时，取出来的便是第n小的，即第n个丑数。

题解

#include<bits/stdc++.h>
using namespace std;
int n,k,ans; 
int s[10001];//存集合 
priority_queue<long long, vector<long long>, greater<long long> > q;//优先队列 
int main()
{    
    cin>>n>>k;//我把n和k反着存的 
    for(int i=1;i<=n;i++)
    {
        cin>>s[i];    
        q.push(s[i]);//进队列 
    }
    for(int i=1;i<=k;i++)
    {
        long long head=q.top();//取队头 
        q.pop();//弹出 
        if(i==k)cout<<head;//第k小就输出 
        for(int j=1;j<=n;j++)
        {
            q.push(head*s[j]);//进队列 
            if(head%s[j]==0)//去重 
            break;
        }
    }
    return 0;
}