当前位置：首页 > news >正文

UVA136 丑数 Ugly Numbers

news 2026/5/12 17:24:57

这道题是经典的“丑数”生成问题。由于需要按顺序找到第 \(1500\) 个丑数，且丑数是由 \(2, 3, 5\) 的乘积构成的，我们可以利用 小根堆（最小优先队列） 来解决。

解题思路

核心思想：
- 丑数序列是递增的。
- 如果我们已经有一个丑数 \(x\)，那么 \(2x, 3x, 5x\) 也是丑数。
- 我们可以从最小的丑数 \(1\) 开始，每次取出当前最小的丑数，生成新的丑数并放入池中，直到取到第 \(1500\) 个。
数据结构：
- 使用 std::priority_queue（配合 greater 实现小根堆）来维护当前的丑数集合，确保每次都能取出最小值。
- 使用 std::set 或者是判断逻辑来去重。因为同一个数可能被多次生成（例如 \(6\) 可以由 \(2 \times 3\) 生成，也可以由 \(3 \times 2\) 生成）。
注意事项：
- 数据可能会溢出 32 位整数，计算过程中建议使用 long long。
- 题目没有输入，程序直接运行并输出结果即可。

C++ 代码实现

这是使用优先队列的简洁写法：

#include <iostream>
#include <vector>
#include <queue>
#include <set>using namespace std;int main() {// 定义小根堆，类型为 long long 防止溢出priority_queue<long long, vector<long long>, greater<long long>> pq;// 使用 set 进行去重set<long long> seen;// 初始化：放入第一个丑数 1pq.push(1);seen.insert(1);long long current_ugly = 0;// 循环提取 1500 次最小值for (int i = 0; i < 1500; ++i) {current_ugly = pq.top(); // 取出堆顶（当前最小值）pq.pop();// 将当前丑数分别乘以 2, 3, 5long long next_vals[3] = {current_ugly * 2, current_ugly * 3, current_ugly * 5};for (long long val : next_vals) {// 如果该数未出现过，则入堆并记录if (seen.find(val) == seen.end()) {seen.insert(val);pq.push(val);}}}// 输出格式必须严格匹配题目要求cout << "The 1500'th ugly number is " << current_ugly << "." << endl;return 0;
}

关键点总结

去重：必须处理重复生成的数字（如 \(6, 10, 15\) 等），否则计数会出错。使用 std::set 是最简单的去重方法。
溢出：虽然第 \(1500\) 个丑数（\(859,963,392\)）在 int 范围内，但在生成后续候选数（如乘以 \(5\)）的过程中可能会短暂超出 int 范围，因此全程使用 long long 更安全。
输出格式：注意题目要求的标点符号，单词 1500'th 中的单引号不能漏掉。