UVa 136 Ugly Numbers【优先队列】

题意：给出丑数的定义，不能被除2,3,5以外的素数整除的的数称为丑数。

和杭电的那一题丑数一样--这里学的紫书上的用优先队列来做。

用已知的丑数去生成新的丑数，利用优先队列的能够每次取出当前最小的丑数再去生成新的丑数====

大概这儿的优先队列就充当了dp转移方程里面的那个min的意思@_@

#include<iostream>  
#include<cstdio>  
#include<cstring>  
#include<algorithm> 
#include<queue>
#include<set>
#include<vector> 
using namespace std;

typedef long long LL;
priority_queue<LL,vector<LL>,greater<LL> >pq;
set<LL>s;

int dir[3]={2,3,5};

int main()
{
    LL x;
    pq.push(1);
    s.insert(1);
    for(int i=1;i<=1500;i++)
    {
        x=pq.top();pq.pop();//将x的值取出，并将其从当前队列中删除 ，以免下次从优先队列中取最小的数时又把它取出来 
        if(i==1500)
        cout<< "The 1500'th ugly number is " <<x<< ".
";
        for(int j=0;j<3;j++)
        {
          LL xx=x*dir[j];
          if(!s.count(xx))  {pq.push(xx);s.insert(xx);}//s.cout(xx)判断xx是否已经存在 
        }
    }
    return 0;
}