CSP-J 2019 第一轮 第 33 题：程序（三）：n=100,b全为1时输出最小值

题目

#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;
}

（4分）当 $n=100$ 时，若 $b$ 数组满足，对任意 $0 \leq i < n$，都有 b[i]=1，那么输出最小为（）。

选项

• A. 582
• B. 580
• C. 579
• D. 581

答案

B

题解

答案是 B. 580。

把递归过程看成一棵二叉树：

• 每次选出区间中的最小值 a[mink]，作为当前节点。
• 左、右两段分别递归，成为左、右子树。
• 根节点的 depth=1，每往下一层，深度加 1。

因为所有 b[i]=1，每个节点的贡献就是 depth，所以输出等于 100 个节点的深度之和。

要让总和最小，就要让节点尽可能放在较浅的层。二叉树第 \(d\) 层最多有 \(2^{d-1}\) 个节点，因此这样安排：

前 6 层共 \(1+2+4+8+16+32=63\) 个，剩余 \(100-63=37\) 个放在第 7 层。

因此最小输出为 \[ 1\times1+2\times2+3\times4+4\times8+5\times16+6\times32+7\times37 =\boxed{580}. \]

这种结构可以通过适当安排 a 的大小实现：让每个子区间的最小值出现在所需的根节点位置即可。