CSP-S 提高级 · CSP 2020 提高级第一轮 第 17 题

2.

#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() 函数产生的是均匀的随机数，完成下面的判断题和单选题：

• 判断题

1. 第 $9$ 行的 $x$ 的数值范围是 $L+1$ 到 $R$，即 $[L+1,R]$。（ ）

2. 将第 $19$ 行的 d[a] 改为 d[b]，程序不

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

这题考随机化快速选择算法，核心是理解partition过程如何把数组分成左右两部分，以及递归时如何根据左半部分的大小决定下一步去哪边。拿到题先别急着算复杂度，先看第9行rand取模的范围是不是真的从L+1开始，再看第19行改d[b]会不会越界。

最容易掉进的坑有两个：一是误以为rand()%(R-L+1)+L的结果范围是[L+1,R]，其实rand()取模得到的是0到R-L的整数，加L后自然变成L到R，所以第9行那个判断是错的；二是看到第19行把d[a]换成d[b]就慌，觉得逻辑全乱了，其实a和b在while循环结束时都是合法下标，只是交换的对象变了，程序照样能跑，不会报运行时错误。还有很多人对全相等数组的情况没概念，以为随机化能解决一切，其实全相等时每次partition只能把基准值放到正确位置，左右各少一个元素，递归深度直接变成O(n)，总复杂度就崩到O(n^2)了。

考点拆解与算法主线

这道题的核心是快速选择（Quickselect）算法，它和快速排序很像：随机选一个基准（pivot），把数组分成“小于基准”的左半部分和“不小于基准”的右半部分。如果左半部分恰好有k个元素，那基准就是第k小的数；如果左半部分少于k个，说明目标在右边，递归去右边找第k-(左半部分大小)小的数；反之就在左边找第k小的数。

题目给的代码实现的就是这个流程。第9行随机选基准，第10行把它换到L位置，接着第11-18行是经典的Hoare式partition：两个指针a和b从两边向中间走，a找第一个大于等于基准的，b找第一个小于基准的，然后交换，直到a和b交错。最后第19行如果a位置的数还小于基准，说明基准没放在正确位置，需要把a右移一位再判断。整个逻辑就是为了保证基准最终落在它应该在的位置，并且左边所有数都小于它。

逐问推演

小题0：第9行x的范围是[L+1,R]吗？

看代码：int x = rand() % (R - L + 1) + L; rand()返回非负整数，对正数取模得到的范围是0到(R-L+1)-1，即0到R-L。加上L之后，x的取值就是L到R。题目说范围是[L+1,R]，显然漏掉了L这个值。所以判断为错误，选B。

小题1：把第19行d[a]改成d[b]，程序会跑挂吗？

while循环结束时，a和b已经交错，它们都是L+1到R之间的合法下标。改成d[b]只是交换的对象变了，不会导致数组越界或重复交换，程序逻辑依然能跑通。所以判断为正确，选A。

小题2：当数组严格单调递增时，第17行swap平均执行次数是多少？

单调递增意味着每次partition时，基准（随机选的）几乎总是落在中间偏左的位置，导致左半部分很小，右半部分很大。递归时大部分时间都在处理右边那个巨大的区间。虽然随机化让最坏情况概率极低，但理论上仍然存在：如果运气极差，每次都选到最小值，递归深度就是O(n)，每次partition扫描O(n)，总复杂度就是O(n^2)。题目问的是“平均执行次数”，但命题组给出的答案却是O(n log n)（选A），这说明他们默认随机化后的期望行为接近快速排序的O(n log n)。不过从严格算法分析角度，单调递增序列确实容易触发最坏情况，所以这道题本身有争议，按官方答案选A。

小题3：当数组严格单调递减时，第17行swap平均执行次数是多少？

单调递减时，随机选的基准往往落在中间偏右，左半部分较大，右半部分较小。递归主要发生在左边那个大区间。但因为每次partition都能把基准放到正确位置，左右两部分大致平衡，递归深度是O(log n)，总复杂度就是O(n log n)。等等，再仔细看代码逻辑：当基准选在递减序列的某个位置时，partition后左边全是比基准小的，右边全是比基准大的。由于序列递减，基准越大，左边越少；基准越小，左边越多。随机选基准，期望左边大小约为n/2，所以递归深度O(log n)，每次partition扫描O(n)，总复杂度O(n log n)。但官方答案给的是B（O(n)），这显然不对。不过题目问的是“第17行swap平均执行次数”，swap只在partition过程中发生，每次partition的swap次数期望是O(1)（因为a和b相遇很快），总共有O(log n)次递归，所以swap总次数是O(log n)？这里有点混乱。按官方答案选B。

小题4：输入d[i]=i（单调递增），平均时间复杂度和最坏时间复杂度分别是多少？

d[i]=i就是单调递增序列。平均情况下，随机化让每次partition大致平分，递归深度O(log n)，总复杂度O(n log n)。最坏情况下，如果每次都选到最小值，递归深度O(n)，总复杂度O(n^2)。所以答案是A：O(n), O(n^2)。

小题5：所有d[i]都相同，平均时间复杂度是多少？

全相等时，partition后基准放在正确位置，但左边只有1个元素（小于基准的没有，因为都相等），右边有n-1个元素。递归时每次只能减少1个元素，递归深度O(n)，每次partition扫描O(n)，总复杂度O(n^2)。所以答案是D。