题目描述 小 K 是一个海港的海关工作人员，他的工作是对货物进出仓库的记录进行统计。 记录分为三种： （1）0 X：入库，其中 XX 是一个整数，表示一个编号为 XX 的货物进入仓库。 （2）1：出库，表示将入库时间离目前最近的货物出库。 （3）2：查询，输出当前仓库内编号最大的货物的编号。 出于分析目的，分析人员在日志中随机插入了若干第三类操作――查询操作。分析日志时，每遇到一次查询操作，都要报告出当前仓库中最大集装箱的编号。 输入描述 包含 n+1n+1 行： 第一行为 11 个正整数 nn，表示有 nn 条记录。 接下来的 nn 行，每行表示 11 条记录，分别属于以下三种格式之一： 入库: 0 X 一次集装箱入库操作，正整数XX表示该次入库的货物的编号 出库: 1 一次集装箱出库操作，（就当时而言）最后入库的集装箱出库 查询: 2 一次查询操作，要求输出当前仓库内编号最大货物的编号 出库时如果仓库为空你应该忽略这次操作；查询时如果仓库为空你应该输出 00。 输出描述 输出若干行，对每次查询操作，用一行输出查询结果。 样例1 输入 13 0 1 0 2 2 0 4 0 2 2 1 2 1 1 2 1 2 输出 2 4 4 1 0 提示 对于 20\%20% 的数据，有 n \le 10n≤10； 对于 40\%40% 的数据，有 n \le 1000n≤1000； 对于 100\%100% 的数据，有 n \le 200000,X \le 10^8n≤200000,X≤10 8 。 C++

<think>哦，这个问题看起来有点挑战性。我得仔细读题目。题目是说，小K要处理仓库的货物记录，有三种操作：入库、出库和查询。我们的任务是在每次查询时输出当前仓库中编号最大的货物编号。那怎么高效处理这些操作呢？ 首先，入库操作很简单，就是添加一个货物。出库操作是弹出最近入库的那个，也就是后进先出的结构，所以可能需要栈。但问题在于查询的时候要找最大值，如果每次查询都遍历整个栈的话，时间复杂度会很高。特别是当n很大的时候，比如2e5次操作，这样的做法肯定会超时。 那这时候我得想有没有更高效的方法。比如，能否维护一个数据结构，使得每次入栈和出栈的时候都能快速更新当前的最大值？这时候我想到可以用一个辅助栈，来记录当前栈中的最大值。比如，主栈保存元素，另一个栈保存对应的最大值。举个例子，当元素入栈时，辅助栈的栈顶是当前的最大值，那么新元素入栈时，比较新元素和当前最大值，取较大的那个作为新的辅助栈的元素。这样，每次查询的时候，辅助栈的栈顶元素就是当前的最大值。这样的话，每次查询的时间复杂度是O(1)，而每次入栈和出栈的时间复杂度也是O(1)，因为辅助栈和主栈同步操作。 那这样的话，具体的实现应该是这样的。主栈保存所有的货物编号，辅助栈保存每个位置对应的当前最大值。当执行入库操作时，将X压入主栈，如果辅助栈为空，那么辅助栈压入X；否则，辅助栈压入max(X, 辅助栈当前栈顶)。这样，每次入栈操作都能维护当前的最大值。出库操作时，主栈和辅助栈同时弹出栈顶元素。查询的时候，如果主栈为空，输出0，否则输出辅助栈的栈顶元素。这应该就能满足题目的要求了。 那这样的方法是否能处理所有情况呢？比如，当有多个相同最大值的情况。比如，栈里有多个相同的最大值，弹出其中一个后，剩下的最大值是否还能正确维护。例如，假设主栈是[2,4,3]，辅助栈是[2,4,4]。这时候弹出栈顶元素3，主栈变为[2,4]，辅助栈变为[2,4]。这时候最大值还是4。如果继续弹出，主栈变为[2]，辅助栈变为[2]。这时候查询得到的最大值是2。这没问题。 那这样的话，这样的数据结构应该能正确维护最大值。那这样的话，这样的方法可行。那现在需要考虑怎么用代码实现这个结构。 用C++的话，可以用两个栈，比如stack<int> main_stack，max_stack。每次执行入库操作0 X时，main_stack.push(X)，然后max_stack.push(max(X, max_stack.empty() ? X : max_stack.top()))。出库的时候，如果main_stack不为空，就两个栈都pop。查询的时候，如果main_stack为空，输出0，否则输出max_stack的栈顶元素。 那这样应该就能处理所有情况了。比如样例输入： 样例输入： 13 0 1 0 2 2 0 4 0 2 2 1 2 1 1 2 1 2 对应的主栈和辅助栈变化如下： 操作序列： 1. 0 1 → main: [1], max: [1] 2. 0 2 → main: [1,2], max: [1,2] 3. 2 → 输出2 4. 0 4 → main: [1,2,4], max: [1,2,4] 5. 0 2 → main: [1,2,4,2], max: [1,2,4,4] 6. 2 → 输出4（max栈顶是4） 7. 1 → 弹出main的最后一个2，max栈顶变为4 → main: [1,2,4], max: [1,2,4] 8. 2 → 输出4 9. 1 → 弹出4 → main: [1,2], max: [1,2] 10. 1 → 弹出2 → main: [1], max: [1] 11. 2 → 输出1 12. 1 → 弹出1 → main为空，max为空 13. 2 → 输出0 所以输出结果应该是样例给出的2、4、4、1、0，对吗？那中间输出的步骤可能对应的查询次数是5次，比如样例的输出有5行？样例的输出是： 2 4 4 1 0 但是原样例的输出是： 2 4 4 1 0 → 总共有5行，但原题中的样例输入是13行操作，其中查询操作出现的次数可能多次。比如输入的记录是13条，其中输出若干行，每遇到查询就输出。所以这样的逻辑是对的。 那这样的方法时间复杂度应该是O(n)，因为每个操作都是O(1)时间，n次操作总时间O(n)。对于n=2e5的情况来说，这样的算法是可以通过的。 那现在代码的结构大致是这样的： 读取n，然后循环处理n次操作。每次操作根据类型处理： 如果是类型0 X，则入栈两个栈。 如果是类型1，则检查主栈是否非空，如果是的话，弹出两个栈顶。 如果是类型2，则检查主栈是否空，输出max栈顶或者0。 但需要注意，出库操作如果仓库为空则忽略。所以在处理类型1的时候，需要判断主栈是否为空，如果空的话不做任何处理。 那这样代码的大致结构就清楚了。接下来是具体的实现。 对于C++来说，使用stack<int>即可。需要注意的是，当处理类型1的时候，如果主栈非空，才弹出两个栈顶。否则忽略。 这样就能处理所有情况了。那这样应该可以解决这个问题。</think>要解决这个问题，我们需要高效地处理三种操作：入库、出库和查询当前最大编号。由于每次查询需要快速获取最大值，直接遍历栈会导致超时。我们可以通过维护两个栈来优化时间复杂度。 ### 方法思路 1. **数据结构选择**：使用两个栈，一个主栈保存所有货物编号，另一个辅助栈同步保存当前栈内的最大值。 2. **入库操作**：将新元素压入主栈，并将当前最大值（新元素与辅助栈顶的较大者）压入辅助栈。 3. **出库操作**：同步弹出两个栈的栈顶元素，确保辅助栈顶始终为当前最大值。 4. **查询操作**：直接返回辅助栈顶元素，若栈为空则输出0。 这种方法使得所有操作的时间复杂度均为$O(1)$，适用于大规模数据。 ### 解决代码 ```cpp #include <iostream> #include <stack> using namespace std; int main() { int n; scanf("%d", &n); stack<int> main_stack; stack<int> max_stack; while (n--) { int op; scanf("%d", &op); if (op == 0) { int x; scanf("%d", &x); main_stack.push(x); if (max_stack.empty()) { max_stack.push(x); } else { max_stack.push(max(x, max_stack.top())); } } else if (op == 1) { if (!main_stack.empty()) { main_stack.pop(); max_stack.pop(); } } else if (op == 2) { if (main_stack.empty()) { printf("0\n"); } else { printf("%d\n", max_stack.top()); } } } return 0; } ``` ### 代码解释 1. **输入处理**：读取操作次数`n`，并逐行处理每个操作。 2. **入库操作（0 X）**：将`X`压入主栈，并根据辅助栈顶更新最大值。 3. **出库操作（1）**：若栈非空，同步弹出主栈和辅助栈顶。 4. **查询操作（2）**：直接输出辅助栈顶（栈空时输出0）。 这种方法确保了所有操作的高效执行，满足题目要求的时间复杂度。