CSP-J 2026 第一轮 第 42 题：平衡分割：④处应填

题目

给定一个长度为 $n$ 的字符串，其中每个字符都是一个十六进制数位。例如，字符串 016A 表示十进制下的四个数 $0, 1, 6, 10$。

现在请选择 $k$ 个（$k$ 是你选定的数）切分位置 $p_{1}, p_{2}, … , p_{k}$，其中 $1 \le k < n$，且 $1 \le p_{1}< p_{2}< \cdots < p_{k}< n$。再令 $p_{0}=0$，$p_{k + 1}=n$。

对于每个 $0 \le i \le k$，计算第 $p_{i} + 1$ 个数到第 $p_{i + 1}$ 个数的平均值，记作 $b_{i}$。你的目标是使 $b_{0}, b_{1}, … , b_{k}$ 中最大值与最小值之差尽可能小，并输出这个最小值。

其中 $2 \le n \le 20$。输入字符串中的字符只可能是 0—9 或 A—F。本题假定字符采用 ASCII 编码。输出答案时保留小数点后 6 位。

以下程序通过递归枚举所有可能的连续分段方案。请补全程序。

#include <algorithm>
#include <iomanip>
#include <iostream>

using namespace std;

constexpr int N = 25;

int n, a[N];
char s[N];

double ans = 1e100;

int value(char c) { return /* ① */; }

void split(int l, int cnt, double mnb, double mxb) {
    if (l > n) {
        if (cnt == 0) return;
        ans = min(ans, mxb - mnb);
        return;
    }
    int sum = 0;
    for (/* ② */) {
        sum += a[r];
        double nwb = /* ③ */;
        split(/* ④ */);
    }
}

int main() {
    cin >> n >> s + 1;
    for (int i = 1; i <= n; ++i)
        a[i] = value(s[i]);
    split(/* ⑤ */);
    cout << fixed << setprecision(6) << ans;

④处应填（ ）。

选项

• A. r + 1, cnt + (r < n), min(mnb, nwb), max(mxb, nwb)
• B. r + 1, cnt + (r <= n), min(mnb, nwb), max(mxb, nwb)
• C. r + 1, cnt + (r < n), max(mnb, nwb), min(mxb, nwb)
• D. r + 1, cnt + (r <= n), max(mnb, nwb), min(mxb, nwb)

答案

A

题解

应选 A：

``cpp r + 1, cnt + (r < n), min(mnb, nwb), max(mxb, nwb) ``

这里每次选取 [l, r] 作为一段，nwb 是这一段的平均值。递归参数分别表示：

• r + 1：下一段从当前位置的后一位开始。
• cnt + (r < n)：cnt 记录切分位置的数量。只有 r < n 时，才在字符串内部新增一个切分位置；r == n 是字符串末尾，不算切分。
• min(mnb, nwb)：更新所有已选段平均值的最小值。
• max(mxb, nwb)：更新所有已选段平均值的最大值。

关键是结束时的这句：

``cpp if (cnt == 0) return; ``

它排除“整个字符串只作为一段”的情况，保证至少切分一次。若用 B 中的 r <= n，末尾也会被算作切分，使不切分的方案被接受，最终答案总会变成 0。