该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目类型

CSP-J 初赛风格阅读程序题。本题共 5 小题，每题只有一个正确选项。

程序

下面的程序读入一个整数序列。程序没有直接说明数组 b 和变量 ans 的实际意义，请根据代码自行推断。

#include <bits/stdc++.h>
using namespace std;

const int N = 100005;
int n, a[N], st[N], b[N], top;
long long ans;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> a[i];

    top = 0;
    for (int i = 1; i <= n; i++) {
        while (top > 0 && a[st[top]] <= a[i])
            top--;
        if (top == 0)
            b[i] = 0;
        else
            b[i] = st[top];
        st[++top] = i;
    }

    ans = 0;
    for (int i = 1; i <= n; i++) {
        if (b[i] == 0)
            ans += i;
        else
            ans += i - b[i];
    }

    cout << ans << '\n';
    return 0;
}

选择区

第 1 题（20 分）

若输入为：

8
4 7 7 3 5 2 8 6

程序输出为（　）。

{{ select(1) }}

• A. 14
• B. 16
• C. 18
• D. 20

第 2 题（20 分）

执行完第一个 for 循环后，b[i] 的含义是（　）。

{{ select(2) }}

• A. i 左侧离 i 最近且值小于 a[i] 的位置，不存在时为 0
• B. i 左侧离 i 最近且值大于 a[i] 的位置，不存在时为 0
• C. i 左侧所有大于 a[i] 的数的个数
• D. i 左侧第一个等于 a[i] 的位置，不存在时为 0

第 3 题（20 分）

每次执行完 st[++top] = i 后，从 st[1] 到 st[top] 观察栈内元素，必然满足（　）。

{{ select(3) }}

• A. 下标严格递减，对应的序列值严格递减
• B. 下标严格递增，对应的序列值严格递增
• C. 下标严格递减，对应的序列值严格递增
• D. 下标严格递增，对应的序列值严格递减

第 4 题（20 分）

若把条件 a[st[top]] <= a[i] 改成 a[st[top]] < a[i]，其余代码不变，则新的 b[i] 表示（　）。

{{ select(4) }}

• A. i 左侧离 i 最近且值大于或等于 a[i] 的位置
• B. i 左侧离 i 最近且值小于或等于 a[i] 的位置
• C. i 右侧离 i 最近且值大于或等于 a[i] 的位置
• D. i 左侧值最大的元素所在位置

第 5 题（20 分）

当 n 个输入整数均可存入 int 时，该程序的时间复杂度和所使用的额外空间复杂度分别是（　）。

{{ select(5) }}

• A. O(n^2)，O(1)
• B. O(n log n)，O(n)
• C. O(n)，O(n)
• D. O(n^2)，O(n)