19116 丑数
### 计划
1. **输入处理**：读取输入的正整数 `T` 和 `T` 行的正整数 `n`。
2. **生成丑数**：使用最小堆（优先队列）生成丑数，确保每次取出的数都是当前最小的丑数。
3. **存储丑数**：将生成的丑数存储在一个数组中，以便快速查找第 `n` 个丑数。
4. **输出结果**：根据输入的 `n`，输出对应的第 `n` 个丑数。
### 伪代码
1. 读取输入 `T` 和 `T` 行的正整数 `n`。
2. 初始化最小堆 `minHeap`，并将初始丑数 `1` 插入堆中。
3. 使用数组 `seen` 记录已经生成的丑数，避免重复。
4. 初始化数组 `uglyNumbers` 用于存储生成的丑数。
5. 循环生成丑数，直到生成足够多的丑数（至少到达最大 `n`）。
6. 每次从堆中取出最小的丑数，并将其乘以 `2`, `3`, `5` 后的结果插入堆中（如果结果不在 `seen` 中）。
7. 将生成的丑数存储在 `uglyNumbers` 数组中。
8. 根据输入的 `n`，输出对应的第 `n` 个丑数。
### C++代码
#include <iostream>
#include <vector>
#include <queue>
#include <set>
using namespace std;vector<long long> generateUglyNumbers(int maxN) {vector<long long> uglyNumbers;priority_queue<long long, vector<long long>, greater<long long>> minHeap;set<long long> seen;minHeap.push(1);seen.insert(1);while (uglyNumbers.size() < maxN) {long long current = minHeap.top();minHeap.pop();uglyNumbers.push_back(current);if (seen.find(current * 2) == seen.end()) {minHeap.push(current * 2);seen.insert(current * 2);}if (seen.find(current * 3) == seen.end()) {minHeap.push(current * 3);seen.insert(current * 3);}if (seen.find(current * 5) == seen.end()) {minHeap.push(current * 5);seen.insert(current * 5);}}return uglyNumbers;
}int main() {int T;cin >> T;vector<int> queries(T);int maxN = 0;for (int i = 0; i < T; ++i) {cin >> queries[i];if (queries[i] > maxN) {maxN = queries[i];}}vector<long long> uglyNumbers = generateUglyNumbers(maxN);for (int i = 0; i < T; ++i) {cout << uglyNumbers[queries[i] - 1] << endl;}return 0;
}