江湖上門派林立,華山派掌門岳不群認為要消除門派的衝突就是要合併各門派,但不能操之過急,必須每次挑兩個門派合併,如此逐步合併,最後將所有門派合併成一派。
合併門派需要一些成本,每個門派都有他的成員數,第 $i$ 個門派的成員數是 $m(i)$,合併兩派的成本就是雙方成員數之和,而兩派合併後,雙方成員就會歸到新合併的門派。
岳不群不希望耗費太多成本,輸入各派人數,請幫他計算最少的合併總成本。
舉例來說,一開始如果有三派,$m=(3, 5, 1)$,若 3 人與 5 人的兩派先合併,成本是 $3+5=8$,合併後剩下兩派,人數是 $(8,1)$,再合併這兩派,成本是 $8+1=9$,此時已經只剩下一派,也就是完成所有合併統一江湖了,總成本是 $8+9=17$。如果我們更換合併的順序,先合併 3 人與 1 人的兩派(成本 4),再合併剩下的 5 人(成本 $4+5=9$), 則總成本只有 $4+9=13$。這是這個例子的最低成本。
第一行是一個正整數 $n$,代表初始的門派數量,
第二行有 $n$ 個正整數是每派的成員數,同行數字間以空白間格。
$n$ 不超過 $2*10^5$,每個門派初始人數都不超過 $10^5$。
第一行輸出總人數,
第二行輸出最小的合併總成本。
3 3 5 1
9 13
編號 | 身分 | 題目 | 主題 | 人氣 | 發表日期 |
沒有發現任何「解題報告」 |