PTA L2-045 堆宝塔：用两个栈模拟游戏过程，C++代码逐行解析

PTA L2-045 堆宝塔双栈模拟的算法艺术与C实现在编程竞赛和数据结构学习中栈Stack作为一种基础却强大的数据结构经常被用来解决各种需要后进先出逻辑的问题。PTA L2-045堆宝塔题目就是一个典型的栈应用场景它要求我们使用两个栈来模拟一个有趣的堆叠游戏过程。这道题不仅考察了对栈特性的理解更考验了如何将实际问题转化为算法实现的能力。1. 理解题目与游戏规则堆宝塔游戏的核心规则可以概括为玩家需要按照特定规则将不同直径的彩虹圈堆叠成宝塔。游戏使用两根柱子——A柱和B柱分别对应我们算法中的两个栈。让我们仔细拆解游戏规则初始状态A柱和B柱都为空第一块彩虹圈直接放在A柱上作为第一座宝塔的基座后续彩虹圈处理与A柱顶部比较如果新彩虹圈直径小于A柱顶部直接叠放在A柱上否则与B柱顶部比较如果B柱为空或新彩虹圈直径大于B柱顶部放在B柱上否则将当前A柱宝塔作为成品移出然后将B柱中所有比新彩虹圈大的圈移到A柱最后将新圈放在A柱上这个规则确保了每个宝塔的彩虹圈直径始终是从下往上递减的。我们需要用算法精确模拟这一过程并最终统计宝塔数量和最高宝塔层数。2. 数据结构设计与算法思路为了高效模拟游戏过程我们选择使用两个vector来代表A柱和B柱。虽然严格来说vector比栈更灵活但在这里我们只使用其栈特性仅在尾部操作。2.1 核心数据结构vectorvectorint res; // 存储已完成的宝塔 vectorint a, b; // a代表A柱b代表B柱2.2 算法流程伪代码while 还有彩虹圈未处理: x 下一个彩虹圈 if a为空: 将x放入a else if x a的顶部: 将x压入a else if b为空 或 x b的顶部: 将x压入b else: 将a作为成品存入res并清空a while b不为空 且 b的顶部 x: 将b的顶部移到a 将x压入a这个逻辑完美对应了游戏规则确保了任何时候A柱和B柱上的彩虹圈都满足特定顺序。3. 完整C代码实现与逐行解析下面我们给出完整的C实现并对关键代码进行详细注释#include bits/stdc.h using namespace std; int main() { vectorvectorint res; // 存储所有完成的宝塔 vectorint a, b; // a是主栈(A柱)b是辅助栈(B柱) int n; cin n; // 读取彩虹圈数量 while (n--) { int x; cin x; // 读取当前彩虹圈直径 // 情况1A柱为空直接放入 if (a.empty()) { a.push_back(x); } // 情况2当前圈比A柱顶部小直接叠放 else if (x a.back()) { a.push_back(x); } // 情况3B柱为空或当前圈比B柱顶部大放入B柱 else if (b.empty() || x b.back()) { b.push_back(x); } // 情况4需要完成当前A柱宝塔并调整B柱 else { res.push_back(a); // 将A柱宝塔作为成品保存 a.clear(); // 清空A柱 // 将B柱中所有比当前圈大的移到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 max_height 0; for (auto tower : res) { max_height max(max_height, (int)tower.size()); } // 输出结果宝塔数量和最高层数 cout res.size() max_height; return 0; }3.1 关键代码段解析输入处理部分int n; cin n; while (n--) { int x; cin x; // ...处理逻辑... }这部分代码读取彩虹圈数量n然后循环读取每个彩虹圈的直径。这种处理方式在算法竞赛中非常常见简洁高效。核心逻辑部分else { res.push_back(a); // 保存完成的宝塔 a.clear(); // 清空A柱 // 调整B柱元素 while (!b.empty() b.back() x) { a.push_back(b.back()); b.pop_back(); } a.push_back(x); // 放入当前圈 }这是算法最复杂的部分当新彩虹圈既不能放在A柱也不能放在B柱时将当前A柱宝塔作为成品保存清空A柱将B柱中所有比当前圈大的移到A柱最后将当前圈放入A柱结果处理部分if (!a.empty()) res.push_back(a); if (!b.empty()) res.push_back(b);循环结束后A柱和B柱上可能还有未处理的彩虹圈需要将它们作为最后的宝塔保存。4. 边界条件与测试用例分析优秀的算法实现必须考虑各种边界情况。让我们分析几个关键测试用例4.1 样例输入分析输入样例11 10 8 9 5 12 11 4 3 1 9 15处理过程分解步骤当前圈A柱状态B柱状态操作说明110[10][]初始放入A柱28[10,8][]810直接放入A柱39[10,8][9]98B柱为空放入B柱45[10,8,5][9]58直接放入A柱512[10,8,5][9,12]125129放入B柱611[12,11][9]1112但119触发宝塔完成74[12,11,4][9]411直接放入A柱83[12,11,4,3][9]34直接放入A柱91[12,11,4,3,1][9]13直接放入A柱109[9][]9199触发宝塔完成1115[15][]159B柱为空放入A柱最终宝塔[10, 8, 5][12, 11, 4, 3, 1][9][15]4.2 特殊边界情况单彩虹圈输入1 5输出应为1 1正确处理了最小输入情况。完全逆序输入5 5 4 3 2 1输出应为1 5所有圈都能直接叠放在A柱上。完全正序输入5 1 2 3 4 5输出应为5 1每个圈都会形成单独的宝塔。5. 算法优化与扩展思考虽然当前实现已经足够高效时间复杂度O(n)空间复杂度O(n)但我们还可以从几个角度进行优化和扩展5.1 代码优化建议减少容器操作res.push_back(a); a.clear();可以替换为res.push_back(move(a)); a vectorint(); // 或者 a.clear()使用move语义避免不必要的拷贝。提前分配内存vectorint a, b; a.reserve(1000); b.reserve(1000);对于已知最大规模的情况提前预留空间可以减少动态扩容的开销。5.2 算法扩展思考多柱问题如果游戏有更多柱子栈算法该如何调整动态规则如果堆叠规则可以动态变化如允许等于的情况如何修改代码可视化出如何修改代码以输出每个宝塔的具体组成// 示例输出每个宝塔的组成 for (int i 0; i res.size(); i) { cout 宝塔 i1 : ; for (int d : res[i]) cout d ; cout endl; }5.3 实际应用场景这种双栈模拟的思路可以应用于许多实际问题浏览器前进后退功能实现撤销/重做操作管理某些类型的任务调度理解这种算法模式有助于我们在面对类似问题时快速找到解决方案。