python/RuMenJingDian/UVa/UVa136.cpp

#include <bits/stdc++.h>

using namespace std;

//宏定义long long ==LL
typedef long long LL;

//丑数的三个特殊值,2,3,5
const int coeff[3] = {2, 3, 5};

int main() {
    //声明一个优先级队列，长整数,greater---> 表示是按大的优先级高
    priority_queue<LL, vector<LL>, greater<LL> > pq;

    //定义一个集合s
    set<LL> s;

    //放入第一个元素,注意，是一对一对放入的
    pq.push(1);
    s.insert(1);

    //开始查找，没有终止值，一直在找
    for (int i = 1;; i++) {
        //找出当前最大的，因为是greater
        LL x = pq.top();
        pq.pop(); //C++的top和pop是分开的，
        //top（）是取出栈顶元素，不会删掉栈里边的元素
        //pop（）是删除栈顶元素。
        if (i == 1500) {
            cout << "The 1500'th ugly number is " << x << ".\n";
            break;
        }
        //0，1，2三个组成元素开始尝试
        for (int j = 0; j < 3; j++) {
            LL x2 = x * coeff[j];
            //如果不存在，放进去，一次放两个
            if (!s.count(x2)) {
                s.insert(x2); //用来记录和查询这个组成元素x2有没有？
                pq.push(x2);  //放入优先级队列
            }
        }
    }
    return 0;
}