訓(xùn)練2　圍欄修復(fù)

題目描述（POJ3253）：約翰想修牧場周圍的籬笆，需要N塊（1≤N≤20000）木板，每塊木板的長度都為Li（1≤Li≤50000，整數(shù)）米。他購買了一塊足夠長的木板（長度為Li的總和，i=1, 2, …, N），以便得到N塊木板，切割時木屑損失的長度不計。唐向約翰收取切割費用，切割一塊木板的費用與其長度相同，切割21米的木板需要21美分。唐讓約翰決定切割木板的順序和位置。約翰知道以不同的順序切割木板，將會產(chǎn)生不同的費用。請幫助約翰確定他得到N塊木板的最低花費。

輸入：第1行包含整數(shù)N，表示木板的數(shù)量。第2..N+1行，每行都包含一個所需木板的長度Li。

輸出：一個整數(shù)，即進行N-1次切割的最低花費。

題解：本題類似哈夫曼樹的構(gòu)建方法，每次都選擇兩個最小的合并，直到合并為一棵樹。每次合并的結(jié)果就是切割的費用。

1. 算法設(shè)計

使用優(yōu)先隊列（最小值優(yōu)先），每次都彈出兩個最小值t1、t2，t=t1+t2，sum+=t，將t入隊，繼續(xù)，直到隊空。sum為所需花費。

2. 算法實現(xiàn)

定義一個優(yōu)先隊列（最小值優(yōu)先），輸入元素入隊。若隊中只有一個元素，則直接累加輸出即可。若隊中多于一個元素，則每次都取兩個最小值，累加和值，并將和值入隊。