CSP-S 2020 第一轮 第23题：将第19行的“d[a]”改为“d[b]”，程序不会发生运行错误。（

题目

#include <iostream>
#include <cstdlib>
using namespace std;

int n;
int d[10000];

int find(int L, int R, int k) {
    int x = rand() % (R - L + 1) + L;
    swap(d[L], d[x]);
    int a = L + 1, b = R;
    while (a < b) {
        while (a < b && d[a] < d[L])
            ++a;
        while (a < b && d[b] >= d[L])
            --b;
        swap(d[a], d[b]);
    }
    if (d[a] < d[L])
        ++a;
    if (a - L == k)
        return d[L];
    if (a - L < k)
        return find(a, R, k - (a - L));
    return find(L + 1, a - 1, k);
}

int main() {
    int k;
    cin >> n;
    cin >> k;
    for (int i = 0; i < n; ++i)
        cin >> d[i];
    cout << find(0, n - 1, k);
    return 0;
}

假设输入的 $n,k$ 和 $d[i]$ 都是不超过 $10000$ 的正整数，且 $k$ 不超过 $n$，并假设 rand() 函数产生的是均匀的随机数，完成下面的判断题和单选题：

将第 $19$ 行的 d[a] 改为 d[b]，程序不会发生运行错误。（ ）

选项

• T. 正确
• F. 错误

答案

T

题解

答案：T（正确）。

关键是分两种情况：

• 当 \(L<R\) 时：初始有 a <= b，循环结束时一定有 a == b。所以把 d[a] 改成 d[b]，判断结果不变。

• 当 \(L=R\) 时：区间只剩一个元素，此时 a=L+1、b=L，不会进入循环。修改后的判断是：

``cpp if (d[L] < d[L]) ++a; ` 条件为假，因此 a-L=1。此时要找的只能是第 1 小的数，即 k=1，接下来直接返回 d[L]`，不会继续递归。

因此，修改后不会导致运行错误，反而避免了单元素区间中原来的 d[a] 可能越界的问题。