记录152#includebits/stdc.h using namespace std; stackint a; // 主栈存储集装箱的重量 stackint b; // 辅助栈存储与主栈对应位置时的当前最大重量 int main(){ ios::sync_with_stdio(false); cin.tie(0); int n, op, x; cin n; while(n--){ cin op; if(op 0){ // 入库操作 cin x; a.push(x); // 如果辅助栈为空或者当前重量大于辅助栈顶压入x否则重复压入栈顶最大值 if(b.empty() || x b.top()){ b.push(x); } else { b.push(b.top()); } } else if(op 1){ // 出库操作 // 题目要求当仓库为空时忽略出库操作 if(!a.empty()){ a.pop(); b.pop(); // 辅助栈同步弹出 } } else { // 查询操作 // 题目要求当仓库为空查询时输出0 if(b.empty()){ cout 0 \n; } else { cout b.top() \n; } } } return 0; }题目传送门https://www.luogu.com.cn/problem/P1165前言我是一名专注信奥赛CSP-J/S、NOIP的教练。如果你觉得这篇题解对你有帮助欢迎点击关注我的CSDN账号我会持续更新高质量算法解析。我深知算法思维的构建远比单纯通过题目更重要本系列题解不局限于AC代码的堆砌而是致力于拆解题目背后的逻辑链条与核心知识点备赛路上若遇瓶颈欢迎随时评论或私信我将甄选典型疑难问题通过视频讲解或撰写专项文章的形式为你提供深度答疑。核心解题思路这道题是一道非常经典的单调栈辅助栈维护最值问题。问题转化与数据结构选择题目明确指出集装箱的进出规则是“先进后出”LIFO这天然对应了数据结构中的栈Stack。我们可以使用一个主栈a来完美模拟集装箱的入库和出库过程。核心难点与算法设计辅助栈维护最大值题目要求在任意时刻都能快速查询当前栈中的最大重量。如果每次查询都去遍历主栈找最大值时间复杂度会达到 O(N) 在 N200000 的数据规模下极易超时。为了解决这个问题我们引入一个辅助栈b。辅助栈的核心思想是辅助栈的栈顶始终记录着当前主栈状态下的最大重量。入栈时将当前重量x与辅助栈当前的最大值即辅助栈栈顶b.top()进行比较。如果x更大说明最大值被刷新了将x压入辅助栈否则说明最大值没变我们将旧的最大值b.top()再次压入辅助栈。这样辅助栈的大小永远和主栈保持一致。出栈时主栈弹出一个元素辅助栈也同步弹出一个元素保证两个栈的状态严格对应。查询时直接读取辅助栈的栈顶元素时间复杂度降为 O(1) 。代码分块详细解释1. 头文件与双栈定义#includebits/stdc.h using namespace std; stackint a; // 主栈存储集装箱的重量 stackint b; // 辅助栈存储与主栈对应位置时的当前最大重量详细分析使用 C STL 中的stack容器。栈a用来忠实记录日志中的集装箱重量栈b是本题的精髓它像一个“影子”一样记录着栈a在每一个历史时刻的最大值。2. 主函数与输入处理int main(){ ios::sync_with_stdio(false); cin.tie(0); int n, op, x; cin n; while(n--){ cin op;详细分析首先进行 IO 加速因为操作总数 NN 达到了 2×1052×105 大量的输入输出可能会导致程序超时。随后读取总操作数 NN 并使用while循环依次处理每一条日志指令。3. 核心逻辑入库操作双栈同步压入if(op 0){ // 入库操作 cin x; a.push(x); // 如果辅助栈为空或者当前重量大于辅助栈顶压入x否则重复压入栈顶最大值 if(b.empty() || x b.top()){ b.push(x); } else { b.push(b.top()); } }详细分析这是维护辅助栈最关键的一步。当重量为x的集装箱入库时主栈a直接压入x。对于辅助栈b我们需要判断当前的x能否打破之前的最大值记录如果辅助栈为空第一个集装箱入库或者x b.top()说明x是新的最大值b压入x。否则x b.top()说明即使加入了x当前的最大值依然是之前的那个最大值。为了保持双栈大小一致我们将b.top()再次压入栈中。这种操作保证了辅助栈b的栈顶永远是当前主栈a所有元素中的最大值。4. 出库操作双栈同步弹出else if(op 1){ // 出库操作 // 题目要求当仓库为空时忽略出库操作 if(!a.empty()){ a.pop(); b.pop(); // 辅助栈同步弹出 } }详细分析当发生出库时主栈a弹出栈顶元素最晚入库的集装箱。此时辅助栈b也必须同步弹出栈顶元素。因为辅助栈记录的是“当前状态”的最大值主栈少了一个元素辅助栈也必须退回到上一个状态的最大值。同时代码严格遵守了题目要求在栈为空时忽略出库操作防止了运行时错误。5. 查询操作与边界处理else { // 查询操作 // 题目要求当仓库为空查询时输出0 if(b.empty()){ cout 0 \n; } else { cout b.top() \n; } } } return 0; }详细分析查询操作变得极其简单只需要输出辅助栈的栈顶b.top()即可时间复杂度为 O(1)。此外代码完美处理了边界情况如果仓库为空即b也为空根据题目要求直接输出 0。核心逻辑总结表代码模块核心变量/操作精炼作用解决的痛点主栈存储stackint a模拟集装箱“先进后出”的进出库流程完美契合题目要求的 LIFO 物理规则辅助栈维护stackint b记录主栈在每一个状态下的历史最大值避免了每次查询都遍历主栈将查询复杂度降为 O(1)入栈逻辑b.push(max(x, b.top()))压入当前元素与旧最大值的较大者保证了辅助栈的大小与主栈严格一致且栈顶始终是当前最大值出栈逻辑a.pop(); b.pop()主栈与辅助栈同步弹出确保在主栈元素减少时辅助栈能准确回退到上一状态的最大值边界防护if(!a.empty())/if(b.empty())处理空栈时的出库与查询防止对空栈进行 pop 或 top 操作导致程序崩溃符合题目输出0的要求