CSP-S 提高级 · CSP 2019 提高级第一轮 第 16 题

二、阅读程序（程序输入不超过数组或字符串定义的范围；判断题正确填√错误填X；除特殊说明外，判断题 $1.5$ 分，选择题 $4$分，共计 $40$ 分）

1.

#include <cstdio>
using namespace std;
int n;
int a[100];

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i)
        scanf("%d", &a[i]);
    int ans = 1;
    for (int i = 1; i <= n; ++i) {
        if (i > 1 && a[i] < a[i - 1])
            ans = i;
        while (ans < n && a[i] >= a[ans + 1])
            ++ans;
        printf("%d\n", ans);
    }
    return 0;
}

• 判断题

1) （1 分）第 16 行输出 $ans$ 时，$ans$ 的值一定大于 $i$。（） 2) （1 分）程序输出的 $ans$ 小于等于 $n$。（） 3) 若将第 12 行的 < 改为 !=，程序输出的结果不会改变。（） 4) 当程序执行到第 16 行时，若 $ans - i> 2$，则 $a[i + 1] \leq a[i]$。 （）

• 选择题

5) （3 分）若输入的 $a$ 数组是一个严格单调递增的数列, 此程序的时间复杂度（） 6) 最坏情况下，此程序的时间复杂度是（）。

这题考数组扫描与双指针，拿到题先盯住 ans 何时重置、while 何时推进，分 i 枚举看 ans 与 i 关系，再代入递增序列验复杂度，别被'最长不下降子序列'带偏。

容易把 ans 当成全局最大值或最长不下降子序列长度；忽略 ans 在遇到下降时立即回退到 i 的'断点重置'；混淆最好情况（递增）与最坏情况（递减）的复杂度；改不等号时以为只影响重置条件而忽略后续 while 的扩展逻辑，导致误判输出不变。

程序功能与双指针逻辑

程序读入一个长度为 n 的数组 a，然后对每个下标 i 输出一个值 ans。ans 的初始值是 1，进入外层循环后，每当遇到 a[i] < a[i-1]（即序列出现下降）时，ans 立刻被重置为 i；接着进入 while 循环，只要 ans < n 且 a[i] >= a[ans+1]，就不断把 ans 右移一位。换句话说，对于固定的 i，ans 最终停在'从 i 开始向右的连续段中，所有元素都不大于 a[i] 的最远位置'，也就是 a[i] 作为局部最大值能覆盖的右端点。

这个机制很像双指针：外层 i 每走一步，内层 ans 要么从 i 重新开始，要么在原有的基础上继续向右扩展，但一旦遇到比 a[i] 大的元素就会停止。关键点在于 ans 只在下降时重置，在上升或持平时会继续推进，因此 ans 始终满足 ans ≥ i。

逐题推演

1) 第 16 行输出 ans 时，ans 的值一定大于 i。（）

直接代入极端情况：n=1，a=[5]。外层 i=1 时，ans 初始为 1，if 条件 i>1 不成立，while 条件 ans<n 也不成立，循环不执行，输出 ans=1。此时 ans=i，并非'大于'。因此命题错误，选 B。

2) 程序输出的 ans 小于等于 n。（）

while 循环的终止条件里明确写了 ans < n，只要条件成立才执行 ++ans，一旦 ans 达到 n 循环立即停止，所以 ans 永远不会超过 n。命题正确，选 A。

3) 若将第 12 行的 < 改为 !=，程序输出的结果不会改变。（）

原条件 a[i] < a[i-1] 只对严格下降触发动作；改成 a[i] != a[i-1] 后，任何相邻不等都会重置 ans=i。考虑严格递增序列 1,2,3：原程序在 i=2 时不会重置，ans 保持 1，while 检查 a[2]>=a[2] 为真，ans 推到 2，再检查 a[2]>=a[3] 为假，输出 2；而改成!=后，i=2 时 a[2]!=a[1] 成立，ans 被重置为 2，while 同样推到 2，输出 2。看似相同，但再看 i=3：原程序 ans 仍为 2，while 检查 a[3]>=a[3] 为真，ans 推到 3，输出 3；改成!=后，i=3 时 a[3]!=a[2] 成立，ans 重置为 3，while 检查 a[3]>=a[4] 为假，输出 3。实际上在严格递增序列中，两种写法输出的 ans 都是 i 本身，因为 while 的扩展条件 a[i]>=a[ans+1] 在 ans=i 时立刻失败（a[i]>=a[i+1] 为假）。因此输出确实不变，命题正确，选 A。

4) 当程序执行到第 16 行时，若 ans - i > 2，则 a[i+1] ≤ a[i]。（）

ans - i > 2 意味着 ans ≥ i+3。由于 ans 是从 i 开始向右扩展的，要能跳到 i+3，while 循环必须至少执行三次，即 a[i] >= a[i+1]、a[i] >= a[i+2]、a[i] >= a[i+3] 都成立。特别地，a[i] >= a[i+1] 等价于 a[i+1] ≤ a[i]。因此命题正确，选 A。