7459. 木棍长度差 (Stick Difference)
时间限制：1000 MS 内存限制：512 MB
题目描述
# 木棍长度差 (Stick Difference) 时间限制：$1.00\text{ s}$ 空间限制：$512\text{ MB}$ ## 题目描述 给你 $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$ 次砍伐后，最长木棍与最短木棍长度差的最小值。 ## 输入输出样例 ### 输入 #1 ```text 3 3 7 3 2 ``` ### 输出 #1 ```text 2 1 2 ``` ## 说明/提示 当 $k=1$ 时，你可以将第一根长度为 $7$ 的木棍砍成长度为 $3$ 和 $4$ 的两根。此时所有木棍长度为 $[3, 4, 3, 2]$，其中最长与最短长度之差为 $2$。 ### 数据规模与约定 - $1 \le n \le 10^5$ - $1 \le m \le 2 \cdot 10^5$ - $1 \le a_i \le 10^9$