Stick Divisions

题目描述

你有一根长度为 x 的木棒，想把它分成 n 根给定长度且总长度为 x 的木棒。 每次操作你可以取任意一根木棒并将其分成两根木棒。该操作的代价为被分割的原始木棒的长度。 要得到这些木棒，最小需要多少代价？

输入格式

输入的第一行包含两个整数 x 和 n：木棒的长度以及要分成的木棒数量。 第二行包含 n 个整数 d_1,d_2,$\ldots$,d_n：分割后每根木棒的长度。

输出格式

输出一个整数：分割所需的最小代价。

8 3
2 3 3

13

提示

$1 \le x \le 10^9$ $1 \le n \le 2 \cdot 10^5$ $\sum d_i = x$ 样例解释：你先把长度为 8 的木棒分成长度为 3 和 5 的两根（代价 8）。之后把长度为 5 的木棒分成长度为 2 和 3 的两根（代价 5）。总代价为 8+5=13。

标签: CSES1161|附加题2

来源

CSES1161|附加题2