登录/注册
217. 栅栏修理 Fence Repair(挑战程序设计竞赛)
时间限制: C/C++ 1000 ms | 其他语言 2000 ms
内存限制: C/C++ 64 MB | 其他语言 128 MB
尝试次数: 372 | 通过次数: 155
尝试人数: 91 | 通过人数: 87
标签: 贪心,优先队列,哈夫曼树
难度: 中等
1
2

我们的目标是将一块完整的木板切割成 nn 块,每块长度为 L1,L2,L3...LnL_1, L_2, L_3 ... L_n。切割后各个木块的长度总和与切割前的木板长度相等。

每次在一块木板上切一刀,代价等于该木板的长度。例如:

  • 在长度为 2121 的木板切一刀,变成两块木板,长度分别为 5,165,16,所需代价为 2121
  • 在长度为 1616 的木板上再切一刀,变为两块木板,长度分别为 8,88, 8,所需代价为 1616

为了达到上述目标,求最小的切割代价是多少。

输入

  • 第一行是整数 n(1n20000)n(1 \leq n \leq 20000),表示要将原始木板切割成多少块
  • 接下来 nn 行,每行一个整数,表示最终每块小木板的长度,其中 1Li500001 \leq L_i \leq 50000

输出

  • 一行,一个整数,表示达到目标所需的最小代价

提示

  • 2021/12/07 测试数据更新,以往通过代码不会重判,可尝试重新提交
样例 1
输入
3
8
5
8
输出
34