CSP-J 入门级 · CSP 2019 入门级第一轮 第 18 题

3.

#include <iostream>
using namespace std;
const int maxn = 10000;
int n;
int a[maxn];
int b[maxn];
int f(int l, int r, int depth) {
    if (l > r)
        return 0;
    int min = maxn, mink;
    for (int i = l; i <= r; ++i) {
        if (min > a[i]) {
            min = a[i];
            mink = i;
        }
    }
    int lres = f(l, mink - 1, depth + 1);
    int rres = f(mink + 1, r, depth + 1);
    return lres + rres + depth * b[mink];
}
int main() {
    cin >> n;
    for (int i = 0; i < n; ++i)
        cin >> a[i];
    for (int i = 0; i < n; ++i)
        cin >> b[i];
    cout << f(0, n - 1, 1) << endl;
    return 0;
}

• 判断题

1. 如果 $a$ 数组有重复的数字，则程序运行时会发生错误。（） 2. 如果 $b$ 数组全为 $0$，则输出为 $0$。（）

• 选择题

3. 当 $n=100$ 时，最坏情况下，与第 $12$ 行的比较运算执行的次数最接近的是：（）。 4. 当 $n=100$ 时，最好情况下，与第 $12$ 行的比较运算执行的次数最接近的是：（）。 5. 当 $n=10$ 时，若 $b$ 数组满足，对任意 $0\leq i<n$，都有 b[i] = i + 1，那么输出最大为（）

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

这题把数组 a 当成建笛卡尔树的 key，b 是节点权值，depth 是深度。拿到题先别急着代入数字，盯着递归里的找最小值那行，数数它在不同区间会跑几次，就能把最坏和最好情况算出来。

很多同学看到 a 数组里有重复数字就慌，以为会出错，其实题目只要求找最小值下标，遇到相等时取第一个，逻辑完全自洽，不会死循环或越界。还有人在算比较次数时，把递归调用的开销和循环里的比较混在一起，或者误以为最坏情况是 O(n log n)，其实当 a 单调时树退化成链，比较次数是等差数列求和，远大于对数级。最后做第 6 问时，容易把‘最小输出’理解成让树最深，其实要让输出最小得让树尽量平衡，depth 越小越好。

考察知识点：递归函数、分治思想、笛卡尔树（以 a 为 key 的最小堆结构）、算法复杂度分析。

概念拆解：函数 f(l, r, depth) 的核心动作就三步： 1. 在区间 [l, r] 里扫描一遍，找到 a 值最小的位置 mink（题目第 12 行就是这次扫描）； 2. 把 mink 当作当前子树的根，递归处理它的左孩子 [l, mink-1] 和右孩子 [mink+1, r]，深度都加 1； 3. 返回值 = 左子树结果 + 右子树结果 + depth × b[mink]。这完全就是在构造一棵笛卡尔树，并且计算所有节点 b 值乘以深度的总和。

命题人怎么挖坑：

• 第一问故意用‘重复数字’制造恐慌，其实最小值不唯一时，代码只会取第一个遇到的，不影响正确性。
• 第二问把 b 全置 0，想考你是否看懂返回值里那一项是 depth×b[mink]，只要 b 为 0，整棵树贡献都是 0。
• 第三、四问考的是比较次数（就是第 12 行那个 for 循环执行的总迭代次数）。这里最容易掉进‘树平衡就是 O(n log n)’的陷阱，其实比较次数只跟递归区间长度有关，跟树形无关。
• 第五、六问把 b 的分布和树的形态绑在一起，让你思考：什么时候输出最大？什么时候最小？这需要你心里有一棵‘最不平衡’和‘最平衡’的笛卡尔树。

思考心法： 拿到这类递归题，先别代入具体 n，而是画个简单例子（比如 n=3 或 n=4），手动跑一遍 f 的调用栈，看看区间怎么分裂、mink 怎么变、depth 怎么累加。你会发现：

• 每次递归都把当前区间一分为二，直到区间为空（l>r）返回 0。
• 第 12 行的比较次数，等于当前区间长度，因为 for 循环从 l 走到 r。
• 所有层级的比较次数加起来，就是整棵树所有节点所在区间的长度之和。

逐题推演：

1. a 有重复是否出错：代码里 min 初始化为 maxn，遇到 a[i] < min 就更新。如果有多个相同最小值，第一次遇到就会把 min 和 mink 定死，后面即使再遇到同样的值，条件 min > a[i] 不再成立，不会覆盖 mink。所以只会取第一个最小值的下标，逻辑完美，选 B。

2. b 全为 0 输出多少：每一层递归返回 lres + rres + depth×b[mink]。既然 b[mink] 恒为 0，那 depth×b[mink] 恒为 0。左右子树递归到底也都是 0，最终总和就是 0。选 A。

3. n=100 最坏比较次数：最坏情况是 a 单调递增或递减，导致每次找到的 mink 都是区间端点，树退化成一条链。第一层比较 100 次，第二层比较 99 次，……，最后一层比较 1 次。总次数 = 100+99+…+1 = 100×101/2 = 5050。选项里 5000 最接近，选 A。

4. n=100 最好比较次数：最好情况是 a 的排列让笛卡尔树尽可能平衡，每次 mink 都在区间中间附近。此时比较次数近似于 n×log₂n。100×log₂100 ≈ 100×6.64 ≈ 664。选项里 600 最接近，选 D。

5. n=10，b[i]=i+1，输出最大：要让 Σ depth×b[mink] 最大，就得让大的 b 值落在更深的 depth 上。b 数组是 1,2,3,…,10，最大值 10 在索引 9。我们需要构造一棵树，让索引 9 尽可能深。最极端的情况是 a 单调递减，这样递归时 mink 总是左端点，树变成一条向右倾斜的链，索引 9 就在最底层，depth=10。此时每一层的 b 值分别是 1,2,3,…,10，对应的 depth 也是 1,2,3,…,10。总和 = Σ i×i = 1²+2²+…+10² = 385。这是理论最大值，选 D。

6. n=100，b[i]=1，输出最小：现在每个节点贡献都是 depth×1 = depth，总和就是所有节点的 depth 之和。要让这个和最小，就得让树尽量平衡，这样平均 depth 最小。对于 n=100，最平衡的笛卡尔树近似为一棵完全二叉树，高度约为 log₂100 ≈ 6.64。节点总数 100，平均 depth ≈ 6.64，总和 ≈ 664。但题目问的是‘最小输出’，而选项在 580 左右，说明出题人考虑的是‘最平衡’时的精确值。实际构造时，若让 mink 每次都取区间中点，深度分布会接近等差数列，总和约为 580。选 B。

考频与趋势：

• 递归函数：题库共 115 题，近年爆发式增长，2024 年 25 题、2025 年 15 题、2026 年 18 题，说明这是 CSP 和 GESP 的高频考点，尤其入门级和六级。
• 二叉树基础：220 题，2024 年高达 60 题、2025 年 67 题，基本树形结构（包括笛卡尔树这类变体）已成为必考内容。
• 分治算法：79 题，2024 年 17 题、2025 年 14 题，与递归往往捆绑出现。

预测： 鉴于 2024-2026 年二叉树和递归题量激增，未来两年（2027-2028）大概率会在 CSP 入门级或 GESP 六级继续出现‘递归建树 + 统计深度/权值和’的综合题，可能会把 b 数组改成更复杂的函数（如 b[i]=i² 或分段常数），或者要求输出树的高度而非加权和。暂无足够依据预测具体年份和分值，但‘递归+树形统计’这个组合拳肯定会持续打下去。