题目描述（POJ3253）： 约翰想修牧场周围的篱笆，需要 N 块（1≤ N ≤20000）木板，每块木板的长度都为 L i （1≤ L i ≤50000，整数）米。他购买了一块足够长的木板（长度为 L i 的总和， i =1, 2, …, N ），以便得到 N 块木板，切割时木屑损失的长度不计。唐向约翰收取切割费用，切割一块木板的费用与其长度相同，切割21米的木板需要21美分。唐让约翰决定切割木板的顺序和位置。约翰知道以不同的顺序切割木板，将会产生不同的费用。请帮助约翰确定他得到 N 块木板的最低花费。

输入： 第1行包含整数 N ，表示木板的数量。第2.. N +1行，每行都包含一个所需木板的长度 L i 。

输出： 一个整数，即进行 N -1次切割的最低花费。

题解： 本题类似哈夫曼树的构建方法，每次都选择两个最小的合并，直到合并为一棵树。每次合并的结果就是切割的费用。

1. 算法设计

使用优先队列（最小值优先），每次都弹出两个最小值 t 1 、 t 2 ， t = t 1 + t 2 ，sum+= t ，将 t 入队，继续，直到队空。sum为所需花费。

2. 算法实现

定义一个优先队列（最小值优先），输入元素入队。若队中只有一个元素，则直接累加输出即可。若队中多于一个元素，则每次都取两个最小值，累加和值，并将和值入队。 1HCaIUsQ/3hmwfa24Mv3hmQmpq/eH6ZoKa0PVrSKysEEPJFl2Xvr9UXvC+1YApo1