问题描述
p136相关说明：本题为《算法竞赛入门经典（第2版）》例题 5-7
解法一：优先队列
从初始值 1 开始，根据所有的因数 2,3,5 去不断地生成新的满足条件的丑数 ugly_number ，并加入集合中。由于 set 无法随机访问，因此额外利用一个优先队列的 ugly_pq 来维护接下来要处理的丑数，不断取出下一个最小的丑数。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 |
#include <bits/stdc++.h> using namespace std; using ll = long long; const int factors[] = {2, 3, 5}; int main() { priority_queue<ll, vector<ll>, greater<ll>> ugly_pq; set<ll> ugly_number; ugly_number.insert(1), ugly_pq.push(1); for (int i = 1; i < 1500; ++i) { ll cur_ugly_number = ugly_pq.top(); ugly_pq.pop(); for (auto fac : factors) if (ugly_number.find(cur_ugly_number * fac) == ugly_number.end()) ugly_number.insert(cur_ugly_number * fac), ugly_pq.push(cur_ugly_number * fac); } cout << "The 1500'th ugly number is " << ugly_pq.top() << "." << endl; return 0; } |
|
1 |
#TODO |
