题目类型

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

程序

下面的程序读入一个可能含负数的整数序列。程序没有直接说明 q 和 ans 的实际意义，请根据代码自行推断。

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

const int N = 100005;
int n, q[N];
long long m, a[N], s[N];

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

    cin >> n >> m;
    s[0] = 0;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        s[i] = s[i - 1] + a[i];
    }

    int head = 0, tail = 0;
    int ans = n + 1;

    for (int i = 0; i <= n; i++) {
        while (head < tail && s[i] - s[q[head]] >= m) {
            ans = min(ans, i - q[head]);
            head++;
        }

        while (head < tail && s[q[tail - 1]] >= s[i])
            tail--;

        q[tail++] = i;
    }

    if (ans == n + 1)
        cout << -1 << '\n';
    else
        cout << ans << '\n';

    return 0;
}

选择区

第 1 题（20 分）

若输入为：

8 7
2 -3 4 1 -2 6 -1 2

程序输出为（　）。

{{ select(1) }}

• A. 2
• B. 3
• C. 4
• D. 7

第 2 题（20 分）

对于任意合法输入，程序最终输出的量是（　）。

{{ select(2) }}

• A. 和恰好等于 m 的连续子段个数
• B. 和不小于 m 的所有连续子段长度之和
• C. 和最大的连续子段长度；若序列全为负数则输出 -1
• D. 和不小于 m 的最短连续子段长度；不存在时输出 -1

第 3 题（20 分）

每次执行完 q[tail++] = i 后，从队首到队尾观察 q 中仍保留的下标，必然满足（　）。

{{ select(3) }}

• A. 下标严格递增，对应的前缀和也严格递增
• B. 下标严格递增，对应的前缀和严格递减
• C. 下标严格递减，对应的前缀和严格递增
• D. 下标严格递减，对应的前缀和也严格递减

第 4 题（20 分）

第二个 while 循环会删除满足 s[q[tail - 1]] >= s[i] 的队尾元素。这样做的主要依据是（　）。

{{ select(4) }}

• A. 被删除下标一定无法与当前的 i 构成合法连续子段
• B. 被删除下标对应的前缀和一定小于 0
• C. 对任何未来右端点，新的下标 i 不仅更靠后，而且前缀和不大于被删除项，因此被删除项不可能给出更短且更容易达标的答案
• D. 队列中最多只能保存一个前缀和

第 5 题（20 分）

该程序的时间复杂度和额外空间复杂度分别为（　）。

{{ select(5) }}

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