BCSP-X · 2024 BCSP-X 下半年活动基础知识测评（小学高年级组） 第 16 题

阅读程序（判断题正确选 A，错误选 B；除特殊说明外，判断题 1.5 分，选择题 3 分，共计 40 分）

第 1 题

#include <cstdio>
using namespace std;
int n, ans, stk[8][105], p[8], i, j;
int main() {
    scanf("%d", &n);
    while (n--) {
        scanf("%d%d", &i, &j);
        while (stk[i][p[i]] > j) {
            --p[i];
            ++ans;
        }
        if (stk[i][p[i]] != j) {
            stk[i][++p[i]] = j;
            ++ans;
        }
    }
    printf("%d\n", ans);
    return 0;
}

假设输入的所有数是正整数，其中 $n$ 不超过 $100$，每次 $i$ 不超过 $5$，每次 $j$ 不超过 $100$，完成下面的判断题和单选题：

判断题

1. 若将第 $002$ 行的 using namespace std; 删去，程序仍可以被正常执行，且对于相同的输入数据，输出结果不变。（ ） 2. 若将第 $003$ 行的 int 改为 long long，程序仍可以被正常执行，且对于相同的输入数据，输出结果不变。（ ） 3. 若将第 $013$ 行的 ++p[i] 改为 p[i]++，程序仍可以被正常执行，且对于相同的输入数据，输出结果不变。（ ） 4. 若将第 $014$ 行的 ++ans 改为 ans++，程序仍可以被正常执行，且对于相同的输入数据，输出结果不变。（ ） 5. 程序输出的 ans 值不可能为 $0$。（ ）

选择题

1. 该程序的算法时间复杂度为（ ）。

（本题为阅读程序 / 完善程序，完整题目与测试数据见平台）

这题考的是栈（Stack）的基本操作和算法复杂度。拿到题先别急着看选项，顺着代码走一遍：外层循环处理 n 个请求，内层 while 是在栈顶找比当前值大的元素并弹出，这是典型的“单调栈”找下一个更大值的思路。核心就是理解++p[i]和++ans到底在干什么，以及为什么整体复杂度是线性的。

最容易栽跟头的地方就是误以为每次内层 while 都会把栈清空，或者觉得++p[i]和++ans的顺序会影响结果。其实++p[i]只是把栈顶指针上移，++ans是计数，它们互不干扰。还有人会把这道题和排序算法搞混，时间复杂度想成 O(n^2) 或者 O(n log n)，其实每个元素最多进栈一次、出栈一次，总操作次数是 2n，所以是 O(n)。判断题里改++p[i]成 p[i]++ 会错，因为前者先自增再取值，后者先取值再自增，逻辑完全不一样。

考点直击

这道题考查的是栈（Stack）的基本操作、指针/下标自增的时机差异以及算法时间复杂度分析。

代码逐行拆解

程序定义了一个二维数组 stk[8][105] 和对应的下标数组 p[8]。stk[i][p[i]] 就是第 i 个栈当前的栈顶元素。p[i] 初始为 0，栈空时 p[i] 为 0。

外层 while(n--) 循环处理 n 个请求，每个请求给出一个下标 i 和一个值 j。

1. 寻找并弹出： ``cpp while (stk[i][p[i]] > j) { --p[i]; ++ans; } ` 这段代码的含义是：只要栈顶元素大于当前值 j，就弹出栈顶（--p[i] 让栈顶指针下移），并且每弹出一个元素，答案 ans 就加 1。这实际上是在找 j 在栈中“插入位置”之前所有比它大的元素，这些元素会被 j 覆盖掉（或者说被弹出）。注意这里 ++ans` 是前缀自增，先加后赋值，但在这里只是计数，顺序不影响结果。

2. 插入新元素： ``cpp if (stk[i][p[i]] != j) { stk[i][++p[i]] = j; ++ans; } ` 如果栈顶元素不等于 j（说明栈为空或者栈顶就是 j，此时不需要插入），就把 j 压入栈中。++p[i] 是后缀自增，先取当前 p[i] 的值作为下标，然后 p[i] 自增。压入后，再次 ++ans` 计数。

判断题详解

1. 删去 using namespace std;： 原代码用了 using namespace std;，所以可以省略 std::。删去后，所有变量名（scanf, printf, stk, p 等）依然是全局定义的，不会冲突。程序依然能正常执行，输出不变。答案：A（正确）。

2. int 改为 long long： 题目假设输入都是正整数，n 不超过 100，i 不超过 5，j 不超过 100。ans 最大也就是 2n（每个元素最多进栈一次、出栈一次），即 200。int 通常至少 32767，long long 更是 64 位。数值范围完全够用，改类型不会溢出，也不会影响逻辑。答案：B（错误）。

3. ++p[i] 改为 p[i]++： 这是本题最大的坑！++p[i] 是前缀自增，先让指针上移，再用新值作为下标；p[i]++ 是后缀自增，先用旧值作为下标，再让指针上移。在插入操作中，stk[i][++p[i]] 是合法的栈顶插入，而 stk[i][p[i]++] 会先访问当前栈顶（可能越界），然后才上移，逻辑完全错误，可能导致栈顶元素被错误覆盖或越界。答案：B（错误）。

4. ++ans 改为 ans++： ans 只是计数器，前缀还是后缀自增，最终值一样，不影响逻辑。答案：A（正确）。

5. ans 不可能为 0： 考虑最坏情况：输入全是相同的数，比如 n 个请求都是 (i, 1)。第一个请求进来，栈空，直接插入，ans 加 1；第二个请求，栈顶等于 1，不执行插入，也不执行弹出，ans 不变；以此类推，ans 至少是 1。再考虑特殊情况：如果 n=0，程序直接输出 0，但题目说 n 是正整数，所以 n>=1，ans 至少是 1。答案：A（正确）。

选择题详解

1. 时间复杂度： 每个元素最多进栈一次（++p[i] 执行一次），最多出栈一次（--p[i] 执行一次）。总操作次数是 2n，所以时间复杂度是 O(n)。答案：B。

2. ans 的最大值： 考虑最坏情况：输入是严格递减的序列，比如 n 个请求都是 (i, n, n-1, ..., 1)。第一个元素插入，ans=1；第二个元素比栈顶大，弹出第一个，插入第二个，ans=2；以此类推，每个元素都会触发一次弹出和一次插入，ans 最终是 2n。答案：E（2n）。

总结

这道题的核心就是理解栈的操作和自增的时机。记住：++p[i] 是前缀自增，p[i]++ 是后缀自增，逻辑完全不同。时间复杂度是线性，因为每个元素最多进出栈一次。ans 的最大值是 2n，因为每个元素最多触发一次弹出和一次插入。