十年磨一劍 (AP325 P-4-3)

人們常說「十年磨一劍」來比喻下的功夫深，但是這句話對於華山磨劍坊就不適用了，因為要磨劍的客人非常的多，一把劍如果磨太久，客人等待的時間過長是會被客訴的。華山磨劍坊目前有 \(n\) 筆訂單，每筆訂單要磨一把劍，每把劍所需的時間不盡相同。磨劍師傅每次只能磨一把劍，現在希望每一筆訂單的完成時間之總和能夠最小，希望能找出最好的磨劍順序。

舉例來說，如果有四把劍，磨劍需要的時間分別是 \((3, 1, 3, 4)\)，如果以 \((3, 1, 3, 4)\) 的順序來磨，第一把的完成時間是 \(3\)，第二把完成時間是 \(3 + 1 = 4\)，第三把是 \(3 + 1 + 3 = 7\)，第四把是 \(3 + 1 + 3 + 4 = 11\)，總和是 \(3 + 4 + 7 + 11 = 25\)。如果把順序改成 \((1, 3, 3, 4)\)，那麼完成時間分別是 \((1, 4, 7, 11)\)，總和是 \(23\)，這是這一題最好的解。

輸入格式

第一行是一個正整數 \(n\)，第二行有 \(n\) 個正整數是每一把劍需要的時間，同行數字間以空白間隔。

限制

• \(1 \le n \le 10^5\)。
• 每把劍需要的時間是不超過 \(10^5\) 的正整數。

輸出格式

輸出最小的完成時間總和。

評分說明

每筆計分測資獨立計分，每筆 5 分，共 100 分；範例不計分。

範例輸入

4
3 1 3 4

範例輸出

23

題目來源

本題出自中正大學吳邦一教授所著《AP325－從 APCS 實作題檢測三級到五級》（v1.5）第 4 章 P-4-3，第 114 頁；經作者同意於 AACPOJ 免費公開。教材下載：AP325 講義（Google Drive）；Python 版：AP325-Python（HackMD）。