TopCoder

腦子裝咖哩
想像不出自己 AC 的題目是實作不出來的!雖然想像得出來也不一定可以就是了

User's AC Ratio

89.5% (214/239)

Submission's AC Ratio

49.1% (275/560)

Tags

Description

  全國最大的便利商店正在舉行集點數換獎品的活動,任何參與者皆可以依據其收集到的貼紙點數,換得相對應的獎品。根據該活動的活動辦法,我們知道點數越高所能換得的獎品價值越高;但是,每次兌換獎品時,只限使用一張集點卡上所收集到的點數,不能合併多張集點卡的點數使用。
  小智目前手上共有n張集點卡,為了換取最高價值的獎品,決定尋求科技公司的協助,將這些集點卡上的所有點數合併到單一集點卡上。然而,這家科技公司的服務有兩項規定:1) 一次只能合併兩張集點卡,2) 每次進行合併時,需收取和合併後點數相同數目的手續費。
  例如,若小智手上有3張集點卡,上面的點數分別是1,3,8。若小智第一次合併點數為18的集點卡,則合併後的新集點卡點數為9,同時必須付9元的手續費;接著,小智要合併點數為39的集點卡,合併後的點數為12,且手續費為12元。因此,兩次合併的手續費總和為9+12=21元。但是,若小智第一次合併點數為13的集點卡,則合併後的新集點卡點數為4,且手續費為 4 元;接著,小智合併點數為48的集點卡,合併後的點數為12,且手續費為12元。因此,兩次合併的手續費總和為4+12=16元。
  小智發現不同的合併順序,並不會影響最後合併完成時集點卡上的總點數,但卻會影響合併所需的手續費。請你幫忙小智計算合併n張集點卡的最低手續費。

Input Format

輸入第一行有一個整數 n,代表需要合併的集點卡張數;第二行有n個以空白符號相間隔的正整數,分別代表這n張集點卡原有收集到的點數。同時,輸入資料中,n105,每一張集點卡上原有收集到的點數,皆為小於或等於1000的正整數。

Output Format

請根據輸入的資料,輸出合併這n張集點卡所需最低手續費。

Sample Input 1

3
1 3 8

Sample Output 1

16

Sample Input 2

4
8 3 5 1

Sample Output 2

30

Hints

Problem Source

臺北市105學年度高級中學資訊學科能力競賽程式設計試題第五題
Set by Yihda Yol
2021.07.05 Update: 測資範圍更新($n \le 10 5$,原本沒有註明)

Subtasks

No. Testdata Range Score
1 0~11 100

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 1000 524288 262144 1
1 1000 524288 262144 1
2 1000 524288 262144 1
3 1000 524288 262144 1
4 1000 524288 262144 1
5 1000 524288 262144 1
6 1000 524288 262144 1
7 1000 524288 262144 1
8 1000 524288 262144 1
9 1000 524288 262144 1
10 1000 524288 262144 1
11 1000 524288 262144 1