CSP-J 2019 第一轮 第 32 题：程序（三）：n=10,b[i]=i+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;
}

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

选项

• A. 386
• B. 383
• C. 384
• D. 385

答案

D

题解

答案是 D．385。

函数每次选出区间中 a 的最小值，把它所在的位置作为当前结点，再递归处理左右两段。因此，可以把递归过程看成一棵二叉树，输出为：

\[ \sum_{i=0}^{9}\text{结点 }i\text{ 的深度}\times(i+1) \]

根结点深度为 1。要让这个和最大，就要让较大的权值处在更深的位置。

为什么最大值不超过 385？

将 10 个结点的深度从小到大排列，记为 \(d_1,d_2,\ldots,d_{10}\)。一定有：

\[ d_k\le k \]

因为深度为 \(d_k\) 的结点有 \(d_k-1\) 个祖先，它们的深度都更小。

根据“较大的数与较大的数相乘，总和最大”，有：

\[ \text{输出}\le \sum_{k=1}^{10}k\,d_k \le \sum_{k=1}^{10}k^2=385 \]

这个上界能达到吗？

能。取 a[i] = i + 1，即 a 严格递增。每次最小值都在当前区间最左端，左侧为空，递归只向右进行：

所以最大输出为：

\[ \boxed{1^2+2^2+\cdots+10^2 =\frac{10\times11\times21}{6}=385} \]