最小代价合并

贪心

说明

每次合并最小的两个文件；与哈夫曼构造相同，最终总代价最小。

分析

合并两个文件的代价为它们的大小之和，合并结果还会参与后续操作。先合并最小的两个文件，能避免大文件被反复计入代价；这与哈夫曼树的贪心结构相同。

图解推演

补充文件大小 [2,3,7]，先合并 2+3=5，再合并 5+7=12，总代价为 5+12=17；先合并 3+7=10 则总代价为 10+12=22。每个叶子大小会按所在树的深度被重复计费，小文件放深处使总成本更小。若合并还带固定费用或顺序约束，需要重新证明。

查看图表代码

适用前提与边界

示例反复排序，实际处理大量文件时可换成最小堆。

示例输入与调用

fmt.Println(MergeCost([]int{10, 20, 30}))

运行输出

90

完整 Go 示例

package main

import (
	"fmt"
	"sort"
)

func MergeCost(sizes []int) int {
	sizes = append([]int(nil), sizes...)
	cost := 0
	for len(sizes) > 1 {
		sort.Ints(sizes)
		x := sizes[0] + sizes[1]
		cost += x
		sizes = append(sizes[2:], x)
	}
	return cost
}

func main() {
	fmt.Println(MergeCost([]int{10, 20, 30}))
}