MEGChai MEGChai
  • 文章
    • 随笔
    • 笔记
    • 教程
  • 关于
首页 › 数据结构与算法 › 在线评测 › UVaOJ 136 - Ugly Numbers
AOAPC II

UVaOJ 136 - Ugly Numbers

Chai
2021-11-24 0:00:00在线评测阅读 434

问题描述

p136

原题链接:UVaOJ 136 - Ugly Numbers

相关说明:本题为《算法竞赛入门经典(第2版)》例题 5-7

解法一:优先队列

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

C++
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;
}
Python
1
#TODO
AOAPC II UVaOJ
赞赏 赞(0)
订阅
提醒
guest
guest
0 评论
内嵌评论
查看所有评论
  • 0
  • 0
Copyright © 2020-2023 MEGChai.
  • 文章
    • 随笔
    • 笔记
    • 教程
  • 关于
# 生活 # # 心理 # # 编程 # # 音乐 # # 写作 #
Chai
95
文章
4
评论
58
喜欢
wpDiscuz