UVA.136 Ugly Numbers (优先队列)

题意分析

如果一个数字是2,3,5的倍数，那么他就叫做丑数，规定1也是丑数，现在求解第1500个丑数是多少。

既然某数字2,3,5倍均是丑数，且1为丑数，那么不妨从1开始算起。算完之后2,3,5均为丑数，然后再从2算起，4,5,10均为丑数……直到算到第1500个即可。那么有如下的问题：

如何从算出来的丑数中取出最小的？

如何保证没有计算重复的丑数？

对于第一个问题，可以采用优先队列的方法，即有序的队列，且为升序，每次只需要取出队首元素即可。

第二个问题，可以采用STL中的set容器即可，如果发现有重复的，即count != 0 那么说明这个数字已经算出过了，就不让其加入队列即可。

代码总览

#include <iostream>

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <vector>

#include <queue>

#include <set>

#define nmax

using namespace std;

typedef long long LL;

const int init []= {2,3,5};

int main()

{

    set<LL>s;

    priority_queue<LL,vector<LL>,greater<LL> > pq;

    s.insert(1);

    pq.push(1);

    LL x;

    for(int i =1; ;++i){

         x = pq.top(); pq.pop();

        if(i == 1500) break;

        for(int j  = 0; j<3; ++j){

            LL t = x * init[j];

            if(s.count(t)  == 0){pq.push(t); s.insert(t);}

        }

    }

    printf("The 1500'th ugly number is %lld.\n",x);

    return 0;

}