丑数【优先队列】

　　　　 UglyNumber

描述

丑数是指不能被2,3,5以外的其他素数整除的数(即因子中，只包含2，3，5)。把丑数从小到大排列起来，结果如下：

1,2,3,4,5,6,8,9,10,12,15,…

输入

输入有多组，每组输入一个n(n<=10000)

输出

输出第n个丑数,以换行结尾。

样例输入1

样例输出1

859963392

提示

从小到大生成各个丑数。最小的丑数是1，对于任意丑数x，2x，3x和5x也是丑数。

#include<queue>
#include<vector>
#include<iostream>
#include<algorithm>
#include <map>
#define ll long long
using namespace std;
ll n;
priority_queue<ll, vector<ll>, greater<ll> >q;             //从小到大的优先队列的定义
map<ll, int>mapp;
int main()
{
    while (cin >> n) {
        q.push(1);
        for (int i = 1; i < n; i++)
        {
            ll t = q.top();
            mapp[2 * t]++;           
            mapp[3 * t]++;
            mapp[5 * t]++;
            q.pop();
            if(mapp[2 * t]==1)q.push(2 * t);    //用map来标记，只有标记过一次的数才能放入优先队列
            if(mapp[3 * t]==1)q.push(3 * t);
            if(mapp[5 * t]==1)q.push(5 * t);            
        }
        cout << q.top() << endl;
    }
    return 0;
}

2018-06-04

丑数 【优先队列】

丑数【优先队列】