uva136(优先队列) - c++编程基础

题意：

不能被２，３，５以外的素数整除的数，称为丑数；找出第１５００个丑数；

思路：

用优先队列和map判重；

如果ｘ是丑数，则２ｘ，３ｘ，５ｘ都是丑数；

不停的放出优先队列；

并取出队头（最小的数）ｘ；

要判断这个数是否已经访问过；

找到第１５００个输出；

#include
  
   
#include
   
     #include
    
      #include
     
       #include
       #define ll long long using namespace std; priority_queue
       
         , greater
        
          > q; map
         
           m; int main() { q.push(1); m[1] = 1; int count = 0; while(1) { ll t = q.top(); q.pop(); count++; if(count == 1500) { printf("The 1500'th ugly number is %lld.\n",t); break; } if(!m[t * 2]) { m[t * 2] = 1; q.push(t * 2); } if(!m[t * 3]) { m[t * 3] = 1; q.push(t * 3); } if(!m[t * 5]) { m[t * 5] = 1; q.push(t * 5); } } return 0; }