44 lines
1.1 KiB
C++
44 lines
1.1 KiB
C++
#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;
|
||
} |