Stick Difference

题目描述

给出 n 根长度分别为 a_1,a_2,\dots,a_n 的木棍。你必须对木棍恰好进行 k 次切割，使得木棍数量变为 n + k。 在切割之后，最长和最短木棍长度之间的差应尽可能小。你的任务是计算对于所有 k=1,2,\dots,m 时能达到的最小差值。 切割必须保证木棍的长度为正整数。你可以假设木棍可以被切割 m 次。

输入格式

第一行包含两个整数 n,m：木棍的数量和最多的切割次数。 第二行包含 n 个整数 a_1,a_2,\dots,a_n：木棍的长度。

输出格式

打印一行包含 m 个整数：当恰好进行 k=1,2,\dots,m 次切割时能达到的最小差值。

3 3
7 3 2

2 1 2

提示

$1 \le n \le 10^5$ $1 \le m \le 2 \cdot 10^5$ $1 \le a_i \le 10^9$ 样例解释：当 k=1 时，你可以把第一根木棍切成长度为 3 和 4 的两段。此时，木棍长度为 [3,4,3,2]，最大差为 2。

标签: CSES3401|附加题2

来源

CSES3401|附加题2