You can not select more than 25 topics
Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
This file contains ambiguous Unicode characters that may be confused with others in your current locale. If your use case is intentional and legitimate, you can safely ignore this warning. Use the Escape button to highlight these characters.
# 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 ;
}