全國最大的便利商店正在舉行集點數換獎品的活動,任何參與者皆可以依據其收集到的貼紙點數,換得相對應的獎品。根據該活動的活動辦法,我們知道點數越高所能換得的獎品價值越高;但是,每次兌換獎品時,只限使用一張集點卡上所收集到的點數,不能合併多張集點卡的點數使用。
小智目前手上共有$ n $張集點卡,為了換取最高價值的獎品,決定尋求科技公司的協助,將這些集點卡上的所有點數合併到單一集點卡上。然而,這家科技公司的服務有兩項規定:1) 一次只能合併兩張集點卡,2) 每次進行合併時,需收取和合併後點數相同數目的手續費。
例如,若小智手上有$ 3 $張集點卡,上面的點數分別是$ 1, 3, 8$。若小智第一次合併點數為$ 1 $和$ 8 $的集點卡,則合併後的新集點卡點數為$ 9$,同時必須付$ 9 $元的手續費;接著,小智要合併點數為$ 3 $和$ 9 $的集點卡,合併後的點數為$ 12$,且手續費為$ 12 $元。因此,兩次合併的手續費總和為$ 9 + 12 = 21 $元。但是,若小智第一次合併點數為$ 1 $和$ 3 $的集點卡,則合併後的新集點卡點數為$ 4$,且手續費為 4 元;接著,小智合併點數為$ 4 $和$8 $的集點卡,合併後的點數為$ 12$,且手續費為$ 12 $元。因此,兩次合併的手續費總和為$ 4+ 12 = 16 $元。
小智發現不同的合併順序,並不會影響最後合併完成時集點卡上的總點數,但卻會影響合併所需的手續費。請你幫忙小智計算合併$ n $張集點卡的最低手續費。
輸入第一行有一個整數 $n$,代表需要合併的集點卡張數;第二行有$n$個以空白符號相間隔的正整數,分別代表這$n$張集點卡原有收集到的點數。同時,輸入資料中,$n \le 10 ^ 5$,每一張集點卡上原有收集到的點數,皆為小於或等於$1000$的正整數。
請根據輸入的資料,輸出合併這$n$張集點卡所需最低手續費。
臺北市105學年度高級中學資訊學科能力競賽程式設計試題第五題
Set by Yihda Yol
2021.07.05 Update: 測資範圍更新($n \le 10 5$,原本沒有註明)
No. | Testdata Range | Score |
---|---|---|
1 | 0~11 | 100 |