Vjudge地址移步此处；
题目：
丑数是指不能被2，3，5以外的其他素数整除的数。把丑数从小到大排列起来，结果如下： 1,2,3,4,5,6,8,9,10,12,15…… 求第1500个丑数
无输入
输出：The 1500’th ugly number is x.（x代表数字）；
题目分析：
数据结构： 利用具有自动排序功能的优先队列储存丑数； 算法设计： 暴力循环； 模块设计： 定义与预处理–初始化–计算–输出–return 0;
代码：
#include<queue>
#include<vector>
#include<set>
#include<cstdio>
using namespace std
;
priority_queue
<long long,vector
<long long>,greater
<long long> > uglyn
;
set
<long long> visited
;
int main()
{
uglyn
.push(1);
visited
.insert(1);
for(int i
=1;i
<1500;i
++)
{
long long x
=uglyn
.top();
uglyn
.pop();
if(visited
.count(2*x
)==0) { uglyn
.push(2*x
);visited
.insert(2*x
); }
if(visited
.count(3*x
)==0) { uglyn
.push(3*x
);visited
.insert(3*x
); }
if(visited
.count(5*x
)==0) { uglyn
.push(5*x
);visited
.insert(5*x
); }
}
printf("The 1500'th ugly number is %lld.\n",uglyn
.top());
return 0;
}
要点与细节总结：
利用insert往set里插入数字；priority_queue默认数字大的优先级高，此题中需使数字小的优先级更高，定义方法如代码所示：priority_queue<long long,vector<long long>,greater<long long> > uglyn;
更新于2020.7.3
