主題
題目連結：
題目大意：
給定一正整數 Ｎ （ ２ ≦ Ｎ ≦ ５, ０００ ），代表接下有 Ｎ 個數字（均小於 １００, ０００ ）。
而當執行加法運算時，會有「代價」，其值即為兩者之和。例如， ２ ＋ ９ 的「代價」是 １１ 。
而現在要求這Ｎ個數字彼此相加到剩下一個數字，其可能的最小「代價」。
當 Ｎ ＝ ０ 時，停止程式。
注：一次放兩題是因為，這兩題一模一樣。用同一份程式碼是可以互通的。
範例輸入：
3
1 2 3
4
1 2 3 4
0
範例輸出：
9
19
範例結果：
（［１、２、３］ → １ ＋ ２ → ［３、３］ → ３ ＋ ３ → ［６］ ，總代價為 ３ ＋ ６ ＝ ９）
（［１、２、３、４］ → １ ＋ ２ → ［３、３、４］ → ３ ＋ ３ → ［４、６］ → ４ ＋ ６ → 總代價為 ３ ＋ ６ ＋ １０ ＝ １９ ）
解題思維：
多試幾個範例，不難觀察出：每次作加法的時候，只要每次抓兩個最小的數字相加，最後總共的「代價」會是最小的。
但是每次做完加法就會產生一個新數字，這個數字的大小不固定，因此要怎麼維持數列的有序性、又能快速存取兩個最小的值呢？如果，每一次加完都要使用排序法「重新排序」一次，那麼時間複雜度將達到 Ｏ（Ｔ * Ｎ ^ ２ * log Ｎ）。 Ｔ 是總共要測試的「Ｎ」的數量。
有兩個方法，一個放在明天的題目講，而今天要講的是第二種方法——堆積（Heap）：
堆積（Heap），是一種可以快速存取、刪除最大值（或最小值）以及快速放入新元素的資料結構。堆積時常會被直接稱為「優先佇列」（Priority Queue），但兩者並不一樣。實際上只要符合優先佇列的條件即可被稱為一個優先佇列（參見維基之定義），而堆積只是最常見的實作方式。
其為一棵完全二元樹。如下圖所示，每個節點都是包含自己的子樹裡最小的數字（也可以是最大的數字，但是這裡舉的例子是所謂的「最小堆積」）。
如此一來，存取極值的時間複雜度只有 Ｏ（１） 。但是「刪除頂端元素」和「插入新元素」呢？
先講什麼是「完全二元樹」（Complete Binary Tree）：意指把節點由上到下一層一層來、由左至右的編號，節點的編號不會「跳號」，即是一棵「完全二元樹」。
如下是一棵「完全二元樹」：
而下圖的二元樹，並不是一棵「完全二元樹」（虛線代表沒有那個節點）：
把二元樹如此編號，便可以輕鬆地使用陣列實作二元樹，「完全二元樹」就更不用說了。而如果要存取某個節點的左子樹，只要把當前節點的編號乘以 ２ 再加 １ ；右子樹則是乘以 ２ 再加 ２ 。
——再回來到堆積的「刪除頂端元素」：
正因為是一棵完全二元樹，因此可以用一變數儲存最後一個元素所在的陣列位置。而把第一個元素與最後一個元素交換，再把上述變數 － １，即達到了「刪除」的動作。
但是因為我們把最後一個元素搬到上面，破壞了堆積原有的性質（節點是極值），所以要把現有的二元樹「堆積化」。
其方法為：判斷「原來的」最後一個元素現在的左子樹、右子樹是否小於自己（或大於，看是哪一種堆積）。如果是，把自己跟最小的一邊交換。重複以上步驟直到不符合或是已經到最底部了。以第一張圖為例：
刪除頂端元素會變成以下：
重新「堆積化」後：
以上，又變回了一個堆積。
——而「插入新元素」，與以上步驟雷同：
把新元素放到最後面，然後判斷父節點是否大於（這裡跟上面相反，因為是要讓節點保持「最小」）。如果是，就跟父節點交換，然後重複以上步驟，直到不符或是已經到最頂端。
以上面已經拔除「３」這個元素的堆積為例，讓我們再把「３」加回去。
首先，放在最後面：
因為父節點大於「３」，所以與之交換：
一樣，父節點還是大於「３」，因此再交換：
已經沒有人大於「３」了，因此不用再作交換。這樣便是一個新的堆積。
可以看到「刪除頂端元素」跟「插入新元素」的時間都是由樹的深度決定，因其是一棵完全二元樹，因此時間複雜度皆是 Ｏ（log Ｎ） （以 ２ 為底的對數）。
那麼，了解了什麼是「堆積」以後，這個問題便不是什麼大問題了。
先將讀入的Ｎ個數字建成一個堆積。因為只有一個數字的時候已經是一個堆積了，因此接下來使用「插入」的演算法，把其他數字加進堆積裡。如此一來，堆積就建好了。
再來，連續拔除兩次「頂端元素」，便是我們一開始要的「最小的兩個數」。加在一起，再放進堆積裡。（記得把加在一起的數字總和加進另一變數裡，畢竟我們要求「代價」）
重複拔除的動作並加在一起的動作，直到只剩下一個數字。此時，中途兩兩相加的和之總和即是題目所求。時間複雜度 Ｏ（Ｔ * Ｎ * log Ｎ）。
但是要注意，因為一開始每個數字最大可以到 ９９, ９９９ ，因此加完的代價會超過一般 int 能容納的範圍，因此記得開 long long 長度。（Python 等語言倒是不需擔心，畢竟很ＯＰ）
（因為兩份程式碼長一樣，所以只放一個連結）
