7458. 木棍分割 (Stick Divisions)
时间限制：1000 MS 内存限制：512 MB
题目描述
# 木棍分割 (Stick Divisions) 时间限制：$1.00\text{ s}$ 空间限制：$512\text{ MB}$ ## 题目描述 你有一根长度为 $x$ 的木棍。你希望将它分割成 $n$ 根给定长度的木棍，且这 $n$ 根木棍的长度之和恰好为 $x$。 在每一步操作中，你可以选择任意一根当前的木棍并将它分割成两根。这样一次操作的代价是被分割木棍的原本长度。 请问得到最终这 $n$ 根木棍所需的最小代价是多少？ ## 输入格式 第一行包含两个整数 $x$ 和 $n$：木棍的初始长度以及需要分割出的木棍数量。 第二行包含 $n$ 个整数 $d_1, d_2, \dots, d_n$：每一根最终分割出的木棍的长度。 ## 输出格式 输出一个整数：分割所需的最小总代价。 ## 输入输出样例 ### 输入 #1 ```text 8 3 2 3 3 ``` ### 输出 #1 ```text 13 ``` ## 说明/提示 在样例中，你先将长度为 $8$ 的木棍分割为长度为 $3$ 和 $5$ 的两根（代价为 $8$）。之后，你将长度为 $5$ 的木棍分割为长度为 $2$ 和 $3$ 的两根（代价为 $5$）。总代价为 $8 + 5 = 13$。 ### 数据规模与约定 - $1 \le x \le 10^9$ - $1 \le n \le 2 \cdot 10^5$ - $\sum d_i = x$