UVA136（Ugly Numbers ）

题目描述：UVA136
思路：对于每个丑数x，2x，3x，5*x也是丑数，所以利用优先队列，每次取出最小的一个数然后再利用set容器判断这个数的2倍，3倍，5倍数是否出现，否就添加入优先队列和set容器。（注意：数据要设为long long，int会产生数据溢出）

#include <iostream>
#include <cstdio>
#include <queue>
#include <set>
#include <vector>
#include <iterator>

using namespace std;

typedef long long LL;
LL op[3] = {2,3,5};

int main()
{
    priority_queue< LL,vector<LL>,greater<LL> >pq;//小的数字优先出列，可以理解为急诊的病人允许插队
    set<LL>s;
    pq.push(1);
    s.insert(1);
    for(int cnt = 1;;cnt++){
        LL x = pq.top();pq.pop();
        if(cnt==1500){
            printf("The 1500'th ugly number is %lld.\n",x);
            break;
        }
        for(int i = 0;i<3;i++){
           LL x2 = x*op[i];
           if(s.count(x2)==0){
                s.insert(x2);
                pq.push(x2);
           }
        }
    }
    return 0;
}

思考：这道题主要练习如何去使用STL里面的优先队列，这里用的越小数字优先出列可以应用到以后的数字打表中，例如素数打表，幸运数打表，因为set容器存储利用的是平衡二叉树（RB树）的结构所以可以利用来快速判重，再加数字优先队列就可以完成打表工作。（适合以后的规律题）
附上set的基本操作：
set集合是c++ stl库中自带的一个容器，set具有以下两个特点：

1、set中的元素都是排好序的

2、set集合中没有重复的元素

常用操作：

begin() 　　 返回set容器的第一个元素的地址

end() 　　　　 返回set容器的最后一个元素地址

clear() 　　 删除set容器中的所有的元素

empty() 　　　 判断set容器是否为空

max_size() 　 返回set容器可能包含的元素最大个数

size() 　　　　 返回当前set容器中的元素个数

erase(it) 删除迭代器指针it处元素

insert(a) 插入某个元素