CSP-S 2024 第一轮 第16题：当1000≥d≥b时，输出的序列是有序的。

题目

#include <iostream>
using namespace std;

const int N = 1000;
int c[N];

int logic(int x, int y) {
    return (x & y) ^ ((x ^ y) | (~x & y));
}

void generate(int a, int b, int *c) {
    for (int i = 0; i < b; i++)
        c[i] = logic(a, i) % (b + 1);
}

void recursion(int depth, int *arr, int size) {
    if (depth <= 0 || size <= 1) return;
    int pivot = arr[0];
    int i = 0, j = size - 1;
    while (i <= j) {
        while (arr[i] < pivot) i++;
        while (arr[j] > pivot) j--;
        if (i <= j) {
            int temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
            i++; j--;
        }
    }
    recursion(depth - 1, arr, j + 1);
    recursion(depth - 1, arr + i, size - i);
}

int main() {
    int a, b, d;
    cin >> a >> b >> d;
    generate(a, b, c);
    recursion(d, c, b);
    for (int i = 0; i < b; ++i) cout << c[i] << " ";
    cout << endl;
}

当 $1000 \geq d \geq b$ 时，输出的序列是有序的。（  ）

选项

• T. 正确
• F. 错误

答案

T

题解

选 T，正确。

recursion 实际上是一个限制递归深度的快速排序：

• 选择 arr[0] 为基准 pivot。
• 通过交换，把较小的元素放到左侧，较大的元素放到右侧。
• 对左右两部分继续递归，直到区间长度不超过 1，或者深度 depth 用完。

关键是：每次划分后，两个递归子区间的长度都严格小于原区间长度。 即使每次都出现最不均衡的划分，一条递归路径上的区间长度也最多是：

\[ b \to b-1 \to b-2 \to \cdots \to 1 \]

因此，最多经过 \(b-1\) 次划分就能完成排序。题目给出 \(d\ge b\)，递归深度足够，不会在排序完成前因深度不足而停止。

另外，\(b\le1000\) 保证生成的序列不超过数组容量。logic 如何生成元素不影响快速排序的正确性，所以输出一定是非降序的。