UVaOJ 136 - Ugly Numbers

问题描述

解法一：优先队列

从初始值 1 开始，根据所有的因数 2,3,5 去不断地生成新的满足条件的丑数 ugly_number ，并加入集合中。由于 set 无法随机访问，因此额外利用一个优先队列的 ugly_pq 来维护接下来要处理的丑数，不断取出下一个最小的丑数。

#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;
}

#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;

}

#TODO

#TODO

AOAPC II UVaOJ