题意: 求第 1500 个丑数 (不能被 2,3,5 以外的其他素数整除的数).
思路: 从小到大生成各个丑数, 最小的丑数是 1, 对于任意丑数 x,2x,3x,5x 都是丑数;
因此利用优先队列保存已经生成的丑数, 每次取出最小的丑数, 生成 3 个新的丑数;
但要注意去重, 比如 2,3 都会生成 6, 于是用 set 来存, 判断重复.
- //The 1500'th ugly number is<number>.
- #include "iostream"
- #include "set"
- #include "vector"
- #include "queue"
- #include "functional"
- using namespace std;
- typedef long long LL;
- int main()
- {
- set<LL> s;
- priority_queue<LL, vector<LL>, greater<LL>>pq;// 从小到大
- int cof[3] = { 2,3,5 };
- s.insert(1);
- pq.push(1);
- for (int i = 1;; i++)
- {
- LL x = pq.top();// 取最小的
- //cout << "x=" << x << endl;
- pq.pop();
- if (i == 1500)
- {
- // 输出
- cout << "The 1500'th ugly number is "<< x<<".\n";
- break;
- }
- for (int j = 0; j < 3; j++)
- {
- LL x2;
- x2 = x*cof[j];
- if (!s.count(x2))// 去重
- {
- s.insert(x2);
- pq.push(x2);
- }
- }
- }
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2948326.html