樱桃等级筛选

题目描述

一家樱桃加工厂按直径大小统计了一批樱桃的数量，得到了一个长度为 $n$ 的数组 $A$。$A_i$ 表示某个尺寸区间的樱桃个数。

现在需要将这 $n$ 组樱桃连续地划分成 $m$ 个“等级”。划分后，会得到 $m$ 个等级，每个等级包含若干组樱桃，其樱桃总数分别为 $S_1, S_2, \dots, S_m$。

你的任务是，设计一种划分方案，使得这 $m$ 个等级的樱桃总数的标准差最小。请你输出这个最优划分方案中，每个等级依次包含的组数。

输入格式

第一行输入两个整数 $n$ 和 $m$，分别表示樱桃的总组数（即数组 $A$ 的长度）和需要划分的等级数目。

第二行输入 $n$ 个整数 $A_1, A_2, \dots, A_n$，表示每个尺寸区间的樱桃个数。

输出格式

输出一行，包含 $m$ 个用空格隔开的整数。第 $i$ 个整数表示最优方案中第 $i$ 个等级所包含的连续组数。

样例

样例输入 1

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

样例输出 1

3 3 2 2

样例输入 2

9 3
1 2 3 4 5 6 7 8 9

样例输出 2

5 2 2

提示

样例 1 解释

将 10 组樱桃划分为 4 个等级。最优方案是将它们按 3, 3, 2, 2 的组数划分：

• 等级 1 (前 3 组): $16+40+37=93$
• 等级 2 (接下来 3 组): $20+18+30=68$
• 等级 3 (接下来 2 组): $18+60=78$
• 等级 4 (最后 2 组): $50+37=87$ 这四组数量 $\{93, 68, 78, 87\}$ 的标准差在所有可能的划分方案中是最小的。

数据范围与约定

对于 $100\%$ 的数据，保证：

• $2 < n \le 20$
• $2 \le m < n$
• $0 < A_i < 100$