用C++模拟堆宝塔游戏：PTA L2-045题解与STL vector实战
用C++模拟堆宝塔游戏：PTA L2-045题解与STL vector实战
堆宝塔游戏是一个有趣的逻辑挑战，它要求玩家根据彩虹圈的直径大小，按照特定规则将它们堆叠成宝塔。这个游戏不仅考验玩家的逻辑思维能力，还能帮助我们深入理解C++中STL容器的使用。本文将带你一步步解析PTA L2-045题目，通过模拟游戏过程来掌握vector容器的实战应用。
对于C++初学者来说，理解如何将游戏规则转化为代码逻辑是一个重要的学习过程。我们将从游戏规则分析开始，逐步构建解决方案，最终实现一个完整的程序。在这个过程中，你会看到vector容器如何成为模拟游戏过程的理想工具。
1. 游戏规则解析与逻辑建模
堆宝塔游戏的核心规则可以分解为几个关键操作：放置彩虹圈、转移宝塔和统计结果。让我们先仔细理解这些规则：
- 初始设置：游戏使用两根柱子，A柱用于构建宝塔，B柱作为临时存放区。第一个彩虹圈直接放在A柱上作为第一座宝塔的基座。
- 放置规则：
- 如果新抓取的彩虹圈直径小于A柱顶部彩虹圈，直接放在A柱上
- 否则，检查B柱：
- 如果B柱为空或新彩虹圈直径大于B柱顶部彩虹圈，放在B柱上
- 否则，将A柱当前宝塔作为成品移出，然后将B柱上所有大于当前彩虹圈的圈移到A柱，最后将当前彩虹圈放在A柱上
- 结束处理：所有彩虹圈处理完毕后，A柱和B柱上剩余的圈分别作为最后两座宝塔
为了将这些规则转化为代码逻辑，我们需要考虑几个关键点：
- 数据结构选择：vector容器非常适合模拟柱子，因为它支持高效的尾部操作（push_back和pop_back）
- 状态判断：需要频繁检查容器的empty()状态和back()元素
- 转移操作：当需要将B柱的圈转移到A柱时，需要循环处理直到满足条件
提示：在开始编码前，建议先用纸笔模拟几个简单案例，这有助于理清逻辑流程。
2. STL vector容器选择与特性分析
为什么选择vector来模拟这个游戏？让我们分析vector的几个关键特性如何匹配游戏需求：
尾部操作高效性：
// 典型的vector尾部操作 a.push_back(x); // 在A柱顶部放置彩虹圈 a.pop_back(); // 从A柱顶部移除彩虹圈 int top = a.back(); // 获取A柱顶部彩虹圈直径vector的这些操作时间复杂度都是O(1)，非常适合游戏的频繁顶部操作需求。相比之下，其他容器如deque或list虽然也支持这些操作，但vector在内存连续性和缓存友好性上更有优势。
容量管理：
a.clear(); // 清空A柱，相当于移走一座完整宝塔 a.empty(); // 检查A柱是否为空这些操作让我们能够方便地管理柱子的状态。特别是clear()操作，正好对应游戏中"将A柱宝塔作为成品移出"的规则。
与其他容器的对比：
| 特性 | vector | deque | list |
|---|---|---|---|
| 尾部操作效率 | O(1) | O(1) | O(1) |
| 内存连续性 | 连续 | 分段连续 | 不连续 |
| 随机访问 | O(1) | O(1) | O(n) |
| 中间插入/删除 | O(n) | O(n) | O(1) |
| 适用场景 | 频繁尾部操作 | 频繁头尾操作 | 频繁中间操作 |
从表格可以看出，vector是最适合模拟堆宝塔游戏的容器，因为我们只需要在柱子顶部进行操作。
3. 代码实现与分步解析
现在让我们逐步实现游戏逻辑。我们将代码分解为几个关键部分，并解释每部分的实现思路。
初始设置与输入处理：
#include <bits/stdc++.h> using namespace std; int main() { vector<vector<int>> res; // 存储所有完成的宝塔 vector<int> a, b; // a模拟A柱，b模拟B柱 int n, x; cin >> n; while (n--) { cin >> x; // 处理逻辑将在下面展开 } // 后续处理 }核心游戏逻辑实现：
- A柱为空时的处理：
if (a.empty()) { a.push_back(x); }- 新彩虹圈可以放在A柱顶部的情况：
else if (x < a.back()) { a.push_back(x); }- 需要检查B柱的情况：
else if (b.empty() || x > b.back()) { b.push_back(x); }- 需要转移宝塔的复杂情况：
else { res.push_back(a); // 将A柱宝塔作为成品保存 a.clear(); // 清空A柱 // 将B柱上大于x的圈移到A柱 while (!b.empty() && b.back() > x) { a.push_back(b.back()); b.pop_back(); } a.push_back(x); // 最后放入当前彩虹圈 }游戏结束后的处理：
// 处理剩余的宝塔 if (!a.empty()) res.push_back(a); if (!b.empty()) res.push_back(b); // 统计结果 int mx = 0; for (auto &c : res) { mx = max(mx, (int)c.size()); } cout << (int)res.size() << " " << mx;注意：在将vector的大小转换为输出时，使用(int)强制转换可以避免某些编译器警告，虽然在这个场景中size()返回的值肯定可以安全转换为int。
4. 测试案例分析与调试技巧
为了验证我们的代码是否正确，让我们分析题目提供的样例输入：
输入样例：
11 10 8 9 5 12 11 4 3 1 9 15处理过程分解：
- 初始放入10到A柱：[10]
- 8 < 10，放入A柱：[10,8]
- 9 > 8，检查B柱为空，放入B柱：[9]
- 5 < 9(A柱顶)，放入A柱：[10,8,5]
- 12 > 5，B柱顶为9 < 12，放入B柱：[12]
- 11 > 5，B柱顶为12 > 11，触发转移：
- 保存A柱：[10,8,5]作为第一个宝塔
- 清空A柱
- 从B柱转移12到A柱（12>11）：[12]
- 放入11：[12,11]
- 4 < 11，放入A柱：[12,11,4]
- 3 < 4，放入A柱：[12,11,4,3]
- 1 < 3，放入A柱：[12,11,4,3,1]
- 9 > 1，B柱为空，放入B柱：[9]
- 15 > 9，B柱顶为9 < 15，放入B柱：[15]
- 处理结束：
- A柱：[12,11,4,3,1]作为第二个宝塔
- B柱：[15,9]作为第三个宝塔
- 将B柱倒序放入A柱形成第四个宝塔：[15,9]
输出验证： 宝塔分别为：
- [10,8,5]（3层）
- [12,11,4,3,1]（5层）
- [15]（1层）
- [9]（1层） 总数：4座，最高：5层，与样例输出一致。
常见错误与调试技巧：
- 未处理最后剩余的宝塔：忘记在循环结束后检查A柱和B柱是否还有未处理的彩虹圈。
- 转移逻辑错误：在将B柱圈转移到A柱时，循环条件或顺序错误。
- 层数统计错误：混淆了宝塔数量和最大层数的统计方式。
调试建议：
- 使用小规模测试数据（3-5个彩虹圈）逐步验证
- 在关键决策点添加临时输出，观察程序状态
- 特别注意边界条件（如空柱子、第一个和最后一个彩虹圈）
5. 算法优化与扩展思考
虽然当前的解决方案已经足够高效，但我们还可以考虑一些优化和扩展方向：
时间复杂度分析：
- 每个彩虹圈最多被放入和移出柱子两次
- 所有操作都是O(1)时间复杂度的vector操作
- 整体时间复杂度为O(N)，空间复杂度为O(N)
可能的优化方向：
- 减少容器拷贝：使用移动语义或指针来存储宝塔，避免vector的拷贝开销
- 预分配内存：如果知道彩虹圈的最大数量，可以预先reserve()空间
- 并行处理：对于大规模数据，可以考虑并行处理多个彩虹圈（虽然本题N≤1000不需要）
扩展思考：
- 如果规则变为可以同时查看接下来k个彩虹圈，如何设计更优策略？
- 如果引入更多柱子（如C柱、D柱），游戏规则和算法该如何调整？
- 如何可视化这个堆叠过程，让调试和理解更加直观？
// 优化示例：使用移动语义避免拷贝 else { res.push_back(move(a)); // 使用move转移所有权 a.clear(); // ...其余逻辑不变 }提示：在实际编程竞赛中，像本题这样的规模通常不需要过度优化，清晰正确的逻辑比微小的性能提升更重要。
通过这个完整的实现过程，我们不仅解决了PTA L2-045题目，更重要的是掌握了如何将实际问题转化为代码逻辑的思考方法，以及STL vector容器在实际场景中的应用技巧。这种能力在解决其他算法问题时同样适用。