题目描述

某大型樱桃加工厂使用自动化机械扫描了一批樱桃的尺寸大小。现在获得了直径范围 $[L,H]$ 各个区间所有的樱桃个数统计。现需通过 $m$ 个等级（$m < H - L$）来筛选不同尺寸大小的樱桃，筛选后需使得各等级内的樱桃数量和的标准差最小。

• 输入第一行：两个整数 $n$（樱桃总组数，$2 < n \le 20$）和 $m$（需要的等级数，$2 < m < n$）。
• 输入第二行：长度为 $n$ 的整数序列 $A = [a_0, a_1, \dots, a_{n-1}]$，其中 $a_i$ 表示第 $i$ 组直径对应的樱桃个数（$0 < a_i < 100$）。

输出长度为 $m$ 的序列 $B = [b_0, b_1, \dots, b_{m-1}]$，其中：

1. $b_0$ 表示从 $A$ 的第 $0$ 位开始，顺序取 $b_0$ 个元素作为第 $1$ 个等级；
2. $b_1$ 表示从 $A$ 的第 $b_0$ 位开始，顺序取 $b_1$ 个元素作为第 $2$ 个等级；
3. 依次类推，保证所有元素被分配且所得到的等级和序列和的标准差最小。

问题本质分析

这是一个将长度为 $n$ 的序列分割成 $m$ 段，使得每一段元素之和的标准差最小的分割优化问题。由于 $n \le 20$，可以使用 动态规划 + 枚举 或者 DFS + 剪枝 来搜索最优分割方案。

思路

1. 前缀和：预处理序列 $A$ 的前缀和 $S$，使得任意区间和 $\mathrm{sum}(i,j)=S[j+1]-S[i]$ 能够 $O(1)$ 获得。

2. DFS 枚举与剪枝：递归枚举每一段的长度，维护已分配的段数、当前位置、已经选取的各段和列表。

   • 当分配到第 $m$ 段时，将剩余元素作为最后一段，计算所有段和的标准差。
   • 记录最小标准差的分割方案。
   • 剪枝策略：若当前已分配段数与剩余元素无法满足分段数时剪枝。

3. 标准差计算：对于段和数组 $W=[w_0,w_1,\dots,w_{m-1}]$，其平均值为

   $$\mu = \frac{1}{m} \sum_{k=0}^{m-1} w_k,$$

   标准差为

   

C++

#include <bits/stdc++.h>
using namespace std;

int n, m;
vector<int> A;
vector<int> S; // 前缀和

double best_std = 1e300;
vector<int> best_B;

// 计算区间和 [l, r)
int intervalSum(int l, int r) {
    return S[r] - S[l];
}

void dfs(int pos, int k, vector<int>& W, vector<int>& B) {
    if (k == m - 1) {
        int len = n - pos;
        B.push_back(len);
        W.push_back(intervalSum(pos, n));
        // 计算平均值
        double mu = accumulate(W.begin(), W.end(), 0.0) / m;
        // 计算方差
        double var = 0;
        for (double w : W) var += (w - mu) * (w - mu);
        var /= m;
        double std = sqrt(var);
        if (std < best_std) {
            best_std = std;
            best_B = B;
        }
        B.pop_back(); W.pop_back();
        return;
    }
    // 至少留出 (m-k-1) 个元素，每段至少 1 个
    for (int len = 1; pos + len + (m - k - 1) <= n; ++len) {
        B.push_back(len);
        int w = intervalSum(pos, pos + len);
        W.push_back(w);
        dfs(pos + len, k + 1, W, B);
        B.pop_back(); W.pop_back();
    }
}

int main() {
    cin >> n >> m;
    A.resize(n);
    for (int i = 0; i < n; ++i) cin >> A[i];
    S.assign(n+1, 0);
    for (int i = 0; i < n; ++i) S[i+1] = S[i] + A[i];

    vector<int> W, B;
    dfs(0, 0, W, B);
    for (int x : best_B) cout << x << ' ';
    return 0;
}

Python

import math

# 输入
n, m = map(int, input().split())
A = list(map(int, input().split()))
# 前缀和
S = [0] * (n + 1)
for i in range(n):
    S[i+1] = S[i] + A[i]

best_std = float('inf')
best_B = []

# 区间和
def interval_sum(l, r):
    return S[r] - S[l]

# DFS 枚举
def dfs(pos, k, W, B):
    global best_std, best_B
    if k == m - 1:
        length = n - pos
        B.append(length)
        W.append(interval_sum(pos, n))
        mu = sum(W) / m
        var = sum((w - mu) ** 2 for w in W) / m
        std = math.sqrt(var)
        if std < best_std:
            best_std = std
            best_B = B.copy()
        B.pop(); W.pop()
        return
    # 枚举当前段长度
    for length in range(1, n - pos - (m - k - 1) + 1):
        B.append(length)
        W.append(interval_sum(pos, pos + length))
        dfs(pos + length, k + 1, W, B)
        B.pop(); W.pop()

# 调用 DFS
dfs(0, 0, [], [])
# 输出结果
print(' '.join(map(str, best_B)))

Java

import java.util.*;

public class Main {
    static int n, m;
    static int[] A;
    static int[] S;
    static double bestStd = Double.MAX_VALUE;
    static List<Integer> bestB = new ArrayList<>();

    static int intervalSum(int l, int r) {
        return S[r] - S[l];
    }

    static void dfs(int pos, int k, List<Integer> W, List<Integer> B) {
        if (k == m - 1) {
            int len = n - pos;
            B.add(len);
            W.add(intervalSum(pos, n));
            double mu = W.stream().mapToDouble(x -> x).sum() / m;
            double var = 0;
            for (double w : W) var += (w - mu) * (w - mu);
            var /= m;
            double std = Math.sqrt(var);
            if (std < bestStd) {
                bestStd = std;
                bestB = new ArrayList<>(B);
            }
            B.remove(B.size() - 1);
            W.remove(W.size() - 1);
            return;
        }
        for (int len = 1; pos + len + (m - k - 1) <= n; len++) {
            B.add(len);
            W.add(intervalSum(pos, pos + len));
            dfs(pos + len, k + 1, W, B);
            B.remove(B.size() - 1);
            W.remove(W.size() - 1);
        }
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        m = sc.nextInt();
        A = new int[n];
        for (int i = 0; i < n; i++) A[i] = sc.nextInt();
        S = new int[n+1];
        for (int i = 0; i < n; i++) S[i+1] = S[i] + A[i];
        dfs(0, 0, new ArrayList<>(), new ArrayList<>());
        for (int x : bestB) System.out.print(x + " ");
    }
}

题目内容

某大型樱桃加工厂使用自动化机械扫描了一批樱桃的尺寸大小。现在获得了直径范围 $[L,H]$ 各个区间所有的樱桃个数统计。现在需要通过 $m$ 个等级 $(m<H-L)$ 来筛选不同尺寸大小的樱桃，筛选后需使得各等级内的樱桃数目的标准差最小。

输入描述

第一行输入两个数字，第一个数字表示樱桃的总组数 $n(2<n<= 20)$ ，第二个数字 $m$ 表示需要获取的等级数目 $a$ ，$2<a<n$

第二行输入一个长度为 $H-L+1$ 的数列 $A$ ，$a<H-L+1$，其中的第 $i$ 个元素 $a_i$ ；表示直径为 $L+i$ 樱桃个数 $(i∈[0,H-L])，0< a_i <100$.

输出描述

输出长度为 $m$ 的数列 $B$ ，其中的第 $1$ 个元素 $b_0$ 表示顺序从 $A$ 中取 $b_0$ 个元素，将该尺寸范围内的樱桃作为一个分类等级；第 $2$ 个元素 $b$ 表示顺序从 $A$ 中起始点 $b_0$ 开始取 $b_1$ 个元素，将该尺寸范围内的樱桃作为一个分类等级，依次类推。

样例1

输入

9 3
1 2 3 4 5 6 7 8 9

输出

5 2 2

说明

要把 $9$ 组樱桃分为三组，使得三组樱桃数量和的标准差最小

顺序取数列 $5$ 个元素和为 $1+2+3+4+5=15$

再顺序取数列 $2$ 个元素和 $6+7=13$

再顺序取数列 $2$ 个元素和 $8+9=17$

$[15$ $13$ $17]$ 的平均值为 $15$ ，标准差为 $sqrt((15-15)^2+(15-13)^2+(15-17)^2)/3$，为所有筛选方案中的最小值。

样例2

输入

10 4
16 40 37 20 18 30 18 60 50 37

输出

3 3 2 2

说明

顺序取数列 $3$ 个元素和为 $16+40+37=93$

再顺序取数列 $3$ 个元素和 $20+18+30=68$

再顺序取数列 $2$ 个元素和 $18+60=78$

再顺序取数列 $2$ 个元素和 $50+37=87$

$[93,68,78,87]$ 的平均值为 $81.5$ ，标准差为 $sqrt((93-81.5)^2$$+(68-81.5)^2$$+(78-81.5)^2$$+(87-81.5)^2)/4$ ，为所有筛选方案中的最小值。

提示

测试样例保证输出答案唯一