Huffman樹在編碼中有著廣泛的應(yīng)用。在這里，我們只關(guān)心Huffman樹的構(gòu)造過(guò)程。

給出一列數(shù){pi}={p0,  p1,  …,  pn-1}，用這列數(shù)構(gòu)造Huffman樹的過(guò)程如下：

1.  找到{pi}中最小的兩個(gè)數(shù)，設(shè)為pa和pb，將pa和pb從{pi}中刪除掉，然后將它們的和加入到{pi}中。這個(gè)過(guò)程的費(fèi)用記為pa  +  pb。

2.  重復(fù)步驟1，直到{pi}中只剩下一個(gè)數(shù)。

在上面的操作過(guò)程中，把所有的費(fèi)用相加，就得到了構(gòu)造Huffman樹的總費(fèi)用。

本題任務(wù)：對(duì)于給定的一個(gè)數(shù)列，現(xiàn)在請(qǐng)你求出用該數(shù)列構(gòu)造Huffman樹的總費(fèi)用。



例如，對(duì)于數(shù)列{pi}={5,  3,  8,  2,  9}，Huffman樹的構(gòu)造過(guò)程如下：

1.  找到{5,  3,  8,  2,  9}中最小的兩個(gè)數(shù)，分別是2和3，從{pi}中刪除它們并將和5加入，得到{5,  8,  9,  5}，費(fèi)用為5。

2.  找到{5,  8,  9,  5}中最小的兩個(gè)數(shù)，分別是5和5，從{pi}中刪除它們并將和10加入，得到{8,  9,  10}，費(fèi)用為10。

3.  找到{8,  9,  10}中最小的兩個(gè)數(shù)，分別是8和9，從{pi}中刪除它們并將和17加入，得到{10,  17}，費(fèi)用為17。

4.  找到{10,  17}中最小的兩個(gè)數(shù)，分別是10和17，從{pi}中刪除它們并將和27加入，得到{27}，費(fèi)用為27。

5.  現(xiàn)在，數(shù)列中只剩下一個(gè)數(shù)27，構(gòu)造過(guò)程結(jié)束，總費(fèi)用為5+10+17+27=59。

輸入的第一行包含一個(gè)正整數(shù)n（n< =100）。 

接下來(lái)是n個(gè)正整數(shù)，表示p0,  p1,  …,  pn-1，每個(gè)數(shù)不超過(guò)1000。 

零基礎(chǔ)同學(xué)可以先學(xué)習(xí)視頻課程，包含C/C++、Python、百練、藍(lán)橋杯輔導(dǎo)、算法數(shù)據(jù)結(jié)構(gòu)等課程，提供視頻講解以及配套習(xí)題，還有老師答疑，點(diǎn)擊這里了解課程詳情

藍(lán)橋杯 貪心