题目(材料题)
(2)(平衡分割)
给定一个长度为n的字符串，其中每个字符都是一个十六进制数位。例如，字符串016A表示十进制下的四个数0、1、6、10。
现在请选择$k$个($k$是你选定的数)切分位置$p_1,p_2,...,p_k$，其中$1≤k < n$，且$1≤p_1 < p_2 < ... < p_k < n$。再令$p_0=0,p_{k+1}=n$ 。
对于每个$0≤i≤k$，计算第$p_i+1$个数到第$p_{i+1}$个数的平均值，记作$b_i$。你的目标是使$b_o,b_1,...,b_k$中最大值与最小值之差尽可能小，并输出这个最小值。
其中$2≤n≤20$。输入字符串中的字符只可能是$0$~$9$或$A$~$F$。本题假定字符采用ASCII编码。输出答案时保留小数点后6位。
以下程序通过递归枚举所有可能的连续分段方案。请补全程序。
01 #include <algorithm>
02 #include<iomanip>
03 #include <iostream>
04
05 using namespace std;
06
07 constexpr int N = 25;
08
09 int n, a[N];
10 char s[N];
11
12 double ans = 1e100;
13
14 int value(char c) { return _____①____; }
15
16 void split(int l, int cnt, double mnb, double mxb) {
17 if (l > n) {
18 if (cnt == 0) return;
19 ans = min(ans, mxb - mnb);
20 return;
21 }
22 int sum = 0;
23 for (_____②____) {
24 sum += a[r];
25 double nwb = _____③____;
26 split(_____④____);
27 }
28 }
29
30 int main() {
31 cin >> n >> s + 1;
32 for (int i = 1; i <= n; ++i)
33 a[i] = value(s[i]);
34 split(_____⑤____);
35 cout << fixed << setprecision(6) << ans;
36 return 0;
27 }
关注我们
