1、合并果子 解題報告<問題描述>     在一個果園里，多多已經(jīng)將所有的果子打了下來，而且按果子的不同種類分成了不同的堆。多多決定把所有的果子合成一堆。     每一次合并，多多可以把兩堆果子合并到一起，消耗的體力等于兩堆果子的重量之和。可以看出，所有的果子經(jīng)過n-1次合并之后，就只剩下一堆了。多多在合并果子時總共消耗的體力等于每次合并所耗體力之和。     因為還要花大力氣把這些果子搬回家，所以多多在合并果子時要盡可能地節(jié)省體力。假定每個果子重量都為1，并且已知果

2、子的種類數(shù)和每種果子的數(shù)目，你的任務(wù)是設(shè)計出合并的次序方案，使多多耗費的體力最少，并輸出這個最小的體力耗費值。     例如有3種果子，數(shù)目依次為1，2，9。可以先將1、2堆合并，新堆數(shù)目為3，耗費體力為3。接著，將新堆與原先的第三堆合并，又得到新的堆，數(shù)目為12，耗費體力為12。所以多多總共耗費體力=3+12=15。可以證明15為最小的體力耗費值。 - 輸入文件    輸入文件fruit.in包括兩行，第一行是一個整數(shù)n(1<n<=10000)，表示果子的種類數(shù)。第二行包含n個整數(shù)，用空格分隔，第i個

3、整數(shù)ai(1<ai<=20000)是第i種果子的數(shù)目。 - 輸出文件    輸出文件fruit.out包括一行，這一行只包含一個整數(shù)，也就是最小的體力耗費值。輸入數(shù)據(jù)保證這個值小于231。 - 樣例輸入3 1 2 9 - 樣例輸出15 - 數(shù)據(jù)規(guī)模對于30的數(shù)據(jù)，保證有n<=1000： 對于50的數(shù)據(jù)，保證有n<=5000； 對于全部的數(shù)據(jù)，保證有n<=10000。<算法分析>將這個問題換一個角度描述：給定n個葉結(jié)點，每個結(jié)點有一個權(quán)值Wi，將它們中兩個、兩個合并為樹，假設(shè)每個結(jié)點從根到它的距離是Di，使得最終(

4、wi + di)最小。于是，這個問題就變?yōu)榱私?jīng)典的Huffman樹問題。Huffman樹的構(gòu)造方法如下：(1) 從森林里取兩個權(quán)和最小的結(jié)點(2) 將它們的權(quán)和相加，得到新的結(jié)點，并且把原結(jié)點刪除，將新結(jié)點插入到森林中(3) 重復(fù)(1)，直到整個森林里只有一棵樹。這個方法的正確性可以參見數(shù)據(jù)結(jié)構(gòu)。<數(shù)據(jù)結(jié)構(gòu)>很顯然，問題當中需要執(zhí)行的操作是：(1) 從一個表中取出最小的數(shù) (2) 插入一個數(shù)字到這個表中。支持動態(tài)Extract_Min和Insert操作的數(shù)據(jù)結(jié)構(gòu)，我們可以選擇用堆來實現(xiàn)。堆是一種完全二叉樹，且保證根結(jié)點的值嚴格大于（或小于）其子孫結(jié)點。具體實現(xiàn)方法可以參見數(shù)據(jù)結(jié)構(gòu)。

5、于是整體算法的時間復(fù)雜度為O(nlogn)，空間復(fù)雜度為O(n)。但是，有沒有更好的方法呢？很顯然，每次合并兩個結(jié)點以后，得到的大小是嚴格遞增的，于是我們可以維護兩個表，一個是原數(shù)字A，一個是新加入的數(shù)字B。這樣，每次就一定是在A和B的頭部取數(shù)，在A和B的尾部刪除。這樣，時間復(fù)雜度就降到了O(n)。因為ai <= 20000，所以排序也可以用o(20000)的方法來實現(xiàn)，整體時間復(fù)雜度為O(n)。（感謝BCBill提供這個方法）<代碼清單>#include <fstream>#include <list>#include <algorithm&g

6、t;using namespace std;ifstream fin("fruit.in");ofstream fout("fruit.out");int n;list <int> a, b;void init() int p;fin >> n;for (int i = 0; i < n; i +) fin >> p;a.push_back(p);a.sort();int get() int ans;if (a.empty() ans = b.front(); b.pop_front(); return ans;

7、if (b.empty() ans = a.front(); a.pop_front(); return ans;if (a.front() < b.front() ans = a.front(); a.pop_front(); return ans; else ans = b.front(); b.pop_front();return ans;void work() int p, sum = 0;for (int i = 0; i < n - 1; i +) p = get() + get();b.push_back(p);sum += p;fout << sum << endl;int main() init();work();return 0;<