题目描述

某大型樱桃加工厂使用自动化机械扫描了一批樱桃的尺寸大小。现在获得了直径范围 $[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$ 个等级；

题目内容

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

输入描述

输入描述

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

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

输出描述

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

样例1

输入

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$ 个元素和$10+60=78$ ；再顺序取数列$2$ 个元素和$50+37=81$ 。$[93,68,78,87]$ 的平均值为$81.5$ ，标准差为 $\sqrt{\frac{(93-81.5)^2+(68-81.5)^2+(78-81.5)^2+(87-81.5)^2}{4} } $，为所有筛选方案中的最小值。

样例2

输入

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{\frac{(15-15)^2+(15-13)^2+(15-17)^2}{3} }$，为所有筛选方案中的最小值。