丑数 (using priority_queue) UVA - 136

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int dir[3]={2,3,5};
int main(void)
{
    priority_queue<ll,vector<ll>,greater<ll> >pq;
    set<ll> s;
    pq.push(1);
    s.insert(1);
    for(int i=1;i<=1500;i++)
    {
        ll x=pq.top();pq.pop();
        //printf("%I64d\n",x);
        if(i==1500)
        {
            //printf("The 1500'th ugly number is %I64d.\n",x);
            cout<<"The 1500'th ugly number is "<<x<<".\n";
            break;
        }
        for(int j=0;j<3;j++)
        {
            ll nx=x*dir[j];
            if(!s.count(nx))
            {
                s.insert(nx);
                pq.push(nx);
            }
        }
    }
    return 0;
}
//set s 作为标记功能，s.insert()实现，s.cout()判断是否出现过，比普通开数组能够节约很多的空间，很有好处。priority_queue<ll,vector<ll>,greater<ll> >pq中greater使原本top是最大的，变成最小的，效果和greater反一下，记住就好。