#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。