#STL009. 最小合并账本

最小合并账本

最小合并账本

账本最初记录了 n 组物品,每组有一个非负重量。每次必须任选两组进行合并:若它们的重量为 x、y,则用一组重量为 x+y 的新组代替这两组,并支付 x+y+f 的费用,其中 f 是每次合并都收取的固定手续费。

重复合并,直到只剩一组。求可以达到的最小总费用。手续费只计入费用,不增加新组重量。重量相同的组仍是不同的组,允许重量为 0。当 n=1 时,无需合并,总费用为 0。

输入格式

第一行两个整数 n、f。第二行 n 个非负整数,表示各组重量,顺序任意。

输出格式

输出一个整数,表示最小总费用。

数据范围

  • 1 ≤ n ≤ 200000。
  • 0 ≤ f ≤ 10⁹。
  • 每组初始重量在 [0, 10⁹] 内。
  • 最小总费用不超过 64 位有符号整数的最大值。请使用足够大的整数类型计算。

样例 1

输入:

4 3
1 2 3 4

输出:

28

解释:先合并 1 和 2,支付 1+2+3=6,剩余重量为 3、3、4。再合并两个 3,支付 3+3+3=9;最后合并 4 和 6,支付 4+6+3=13。总费用为 6+9+13=28,这已经是最小值。

样例 2

输入:

1 1000000000
0

输出:

0

解释:账本只有一组,不进行任何合并。即使固定手续费很大,也不会产生费用,因此答案为 0。