TopCoder

FHVirus
想像不出自己 AC 的題目是實作不出來的!

User's AC Ratio

90.8% (197/217)

Submission's AC Ratio

50.4% (254/504)

Tags

Description

  全國最大的便利商店正在舉行集點數換獎品的活動,任何參與者皆可以依據其收集到的貼紙點數,換得相對應的獎品。根據該活動的活動辦法,我們知道點數越高所能換得的獎品價值越高;但是,每次兌換獎品時,只限使用一張集點卡上所收集到的點數,不能合併多張集點卡的點數使用。
  小智目前手上共有$ 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 $張集點卡的最低手續費。

Input Format

輸入第一行有一個整數 $n$,代表需要合併的集點卡張數;第二行有$n$個以空白符號相間隔的正整數,分別代表這$n$張集點卡原有收集到的點數。同時,輸入資料中,$n \le 10 ^ 5$,每一張集點卡上原有收集到的點數,皆為小於或等於$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