使用C++语言完成下列编程题目描述 M 海运公司最近要对旗下仓库的货物进出情况进行统计。目前他们所拥有的唯一记录就是一个记录集装箱进出情况的日志。该日志记录了两类操作：第一类操作为集装箱入库操作，以及该次入库的集装箱重量；第二类操作为集装箱的出库操作。这些记录都严格按时间顺序排列。集装箱入库和出库的规则为先进后出，即每次出库操作出库的集装箱为当前在仓库里所有集装箱中最晚入库的集装箱。 出于分析目的，分析人员在日志中随机插入了若干第三类操作――查询操作。分析日志时，每遇到一次查询操作，都要报告出当前仓库中最大集装箱的重量。 输入格式 包含 N+1 行： 第一行为一个正整数 N，对应于日志内所含操作的总数。 接下来的 N 行，分别属于以下三种格式之一： 格式 1：0 X，表示一次集装箱入库操作，正整数 X 表示该次入库的集装箱的重量。 格式 2：1，表示一次集装箱出库操作，（就当时而言）最后入库的集装箱出库。 格式 3：2，表示一次查询操作，要求分析程序输出当前仓库内最大集装箱的重量。 当仓库为空时你应该忽略出库操作，当仓库为空查询时你应该输出 0。 输出格式 输出行数等于日志中查询操作的次数。每行为一个整数，表示查询结果。 输入输出样例 输入 #1 13 0 1 0 2 2 0 4 0 2 2 1 2 1 1 2 1 2 输出 #1 2 4 4 1 0

<think>好的，我现在需要解决这个编程题目。题目是关于模拟仓库的集装箱进出，并且在查询时输出当前的最大重量。我得仔细看看题目要求，然后思考怎么用C++来实现。 首先，题目中的操作分为三种：入库（0 X）、出库（1）、查询（2）。入库的时候要记录重量，出库是先进后出的结构，所以这应该用栈来模拟。而每次查询需要得到当前栈中的最大值。这时候，问题就变成了如何高效地维护栈中的最大值，因为如果每次查询都遍历整个栈的话，时间复杂度会很高，特别是当操作次数很多的时候，可能会超时。 那怎么高效地维护最大值呢？我记得有一种方法是用一个辅助栈来保存当前的最大值。例如，每当主栈压入一个元素时，辅助栈也压入当前的最大值。这样，每次出栈的时候，辅助栈也同步出栈，这样栈顶始终是当前主栈中的最大值。这种方法的时间复杂度是O(1)的，每个操作都是常数时间，应该可以满足题目的需求。 那具体怎么实现呢？假设主栈是stk，辅助栈max_stk。当压入一个元素x的时候，如果max_stk为空，那么压入x；否则，比较x和当前max_stk的栈顶元素，压入较大的那个。这样，max_stk的栈顶始终是当前的最大值。这样，在每次查询的时候，直接取max_stk的栈顶即可。当执行出栈操作时，主栈和辅助栈同时弹出。这样就能保证两者的同步。 那现在需要考虑各种情况。例如，当仓库为空的时候，出库操作要忽略。而查询的时候，如果栈为空，输出0。这些情况在代码中需要处理。 接下来，输入的解析部分。输入的第一行是N，接下来N行，每一行是操作。对于每一行，需要判断操作类型。例如，如果是0，后面跟着X，那么是入库操作；如果是1，是出库操作；如果是2，是查询操作。 现在，我需要考虑如何处理输入。可以使用C++的标准输入，比如用cin来读取。对于每一行，可以先读取操作类型，然后根据类型处理后续的数据。例如，对于操作0，读取X的值。 那么，具体步骤大概是这样的： 1. 读取N。 2. 初始化两个栈：主栈stk和辅助栈max_stk。 3. 对于每个操作： a. 如果是类型0（入库）： i. 读取X。 ii. 将X压入stk。 iii. 如果max_stk为空，则压入X；否则，压入max(X, max_stk.top()). b. 如果是类型1（出库）： i. 检查stk是否为空。如果为空，跳过。 ii. 否则，弹出stk和max_stk的栈顶。 c. 如果是类型2（查询）： i. 如果stk为空，输出0。 ii. 否则，输出max_stk.top()。 4. 将所有查询的结果依次输出。 接下来，测试一下样例输入是否正确处理。例如，样例输入中的情况： 输入： 13 0 1 → 入库1，stk=[1], max_stk=[1] 0 2 → 入库2，stk=[1,2], max_stk=[1,2] 2 → 查询，输出2 0 4 → stk=[1,2,4], max_stk=[1,2,4] 0 2 → stk=[1,2,4,2], max_stk=[1,2,4,4] 2 → 查询，输出4 1 → 出库，栈顶变为2。stk=[1,2,4], max_stk=[1,2,4] 2 → 查询，输出4 1 → 出库，栈变成[1,2], max_stk变为[1,2] 1 → 出库，栈变成[1], max_stk变为[1] 2 → 查询，输出1 1 → 出库，栈空 2 → 查询，输出0 输出结果应该是2，4，4，1，0。这与样例给出的输出一致，所以这个逻辑是正确的。 那现在编写代码的时候需要注意什么？比如，栈的弹出需要判断是否为空。例如，当执行出库操作时，如果栈是空的，就忽略。否则，弹出两个栈的栈顶元素。同样，查询的时候，如果栈为空，输出0。 另外，关于输入的处理，需要处理每一行的操作。例如，对于类型0，后面跟着一个数X。这时候可以用cin读取第一个数，如果是0，则继续读取第二个数。比如，可以用类似这样的代码： int op; cin >> op; if (op == 0) { int x; cin >> x; // 处理入库 } else if (op == 1) { // 处理出库 } else if (op == 2) { // 处理查询 } 但是需要注意，当输入行中包含多个数字的时候，比如“0 123”，这时候cin会正确读取第一个作为操作类型，第二个作为X。其他类型不会有问题。 那现在编写代码的结构： #include <iostream> #include <stack> using namespace std; int main() { int N; cin >> N; stack<int> stk; stack<int> max_stk; vector<int> output; // 保存查询结果，最后统一输出 for (int i=0; i<N; ++i) { int op; cin >> op; if (op == 0) { int x; cin >> x; stk.push(x); if (max_stk.empty()) { max_stk.push(x); } else { max_stk.push(max(x, max_stk.top())); } } else if (op == 1) { if (!stk.empty()) { stk.pop(); max_stk.pop(); } } else if (op == 2) { if (stk.empty()) { output.push_back(0); } else { output.push_back(max_stk.top()); } } } for (int num : output) { cout << num << endl; } return 0; } 这样应该可以解决问题。需要注意的是，当栈为空时，出库操作被忽略。查询时如果栈为空，输出0。辅助栈max_stk与主栈同步弹出和压入。这样就能保证每次查询的时候，max_stk的栈顶就是当前的最大值。 现在，检查一下可能的边界情况： 1. 当仓库一直为空时，所有出库操作都被忽略，所有查询返回0。 2. 当连续入库多个元素，最大值正确更新。 3. 当出库操作后，最大值正确回到之前的状态。 4. 当所有元素都被出库后，查询返回0。 例如，测试案例中的最后一个查询，仓库已经空了，所以输出0。 综上，这个方案应该是正确的。</think>要解决这个问题，我们需要模拟仓库的集装箱进出操作，并在查询时快速返回当前仓库中的最大集装箱重量。由于操作遵循先进后出的规则，我们可以使用栈结构来高效处理。同时，为了快速获取最大值，可以维护一个辅助栈来跟踪当前栈中的最大值。 ### 方法思路 1. **使用两个栈**：一个主栈用于记录集装箱的进出顺序，另一个辅助栈用于记录当前主栈中的最大值。 2. **入库操作**：将集装箱重量压入主栈，并根据辅助栈顶的值更新当前最大值并压入辅助栈。 3. **出库操作**：从主栈弹出顶部元素，同时弹出辅助栈顶元素以保持同步。 4. **查询操作**：直接返回辅助栈的栈顶元素，若主栈为空则返回0。 这种方法确保每个操作的时间复杂度为O(1)，从而高效处理大量操作。 ### 解决代码 ```cpp #include <iostream> #include <stack> #include <vector> using namespace std; int main() { int N; cin >> N; stack<int> stk; // 主栈，存储集装箱重量 stack<int> max_stk; // 辅助栈，存储当前最大值 vector<int> output; // 存储查询结果 for (int i = 0; i < N; ++i) { int op; cin >> op; if (op == 0) { int x; cin >> x; stk.push(x); if (max_stk.empty() || x > max_stk.top()) { max_stk.push(x); } else { max_stk.push(max_stk.top()); } } else if (op == 1) { if (!stk.empty()) { stk.pop(); max_stk.pop(); } } else if (op == 2) { if (stk.empty()) { output.push_back(0); } else { output.push_back(max_stk.top()); } } } for (int num : output) { cout << num << endl; } return 0; } ``` ### 代码解释 1. **输入处理**：读取操作总数N，并逐行处理每个操作。 2. **入库操作**（0 X）：将重量X压入主栈，并根据辅助栈顶更新最大值并压入辅助栈。 3. **出库操作**（1）：若主栈非空，则弹出主栈和辅助栈顶元素。 4. **查询操作**（2）：若主栈非空，输出辅助栈顶元素；否则输出0。 5. **结果输出**：将查询结果依次输出。 这种方法通过维护辅助栈高效跟踪当前最大值，确保了每个操作的高效执行。