731 . 霍夫曼編碼

Submit
Status
Discussion / Solution
Ranklist
Back to Problems List

TopCoder

joycewang

User's AC Ratio

80.0% (8/10)

Submission's AC Ratio

25.6% (10/39)

Tags

apcsc apcsc-greedy

Description

假設今天英文字母只有 a, b, c, d 四種，我們可以用以下表格把英文字母轉成二進位：

字母
二進位表示
a
00
b
01
c
10
d
11

例如字串 aaabbcd 會變成 00000001011011，但是如果今天我們換一個二進位轉換：

字母
二進位表示
a
0
b
10
c
110
d
1111

那 aaabbcd 會轉換成 00010110111，比剛剛的短了不少，以電腦來說，佔用的記憶體也變得更少。
在設計轉換方式時，首先要注意到我們不能造成混肴 — 不能有一個字母的二進位轉換是另外一個字母的二進位轉換前綴，如果 0 代表 a，00 代表 b，那我們無法分辨 aa 和 b。另外，很明顯的，我們只在乎每個字母出現的次數，而不在乎他們出現的順序。
現在給你一個字串中每個字母出現的次數，請找到一個二進位轉換方式使得這個字串轉換成二進位後最短，並輸出轉換後的二進位字串長度。

Input Format

輸入第一行有一個正整數 $N$，代表字母的種類數。接下來一行有 $N$ 個以空格分隔的整數 $A_1, A_2, \ldots, A_N$，代表每個字母各自在字串中出現的次數。

  • $1 \le N \le 10^ 5$
  • $1 \le A_1 \le A_2 \le \cdots \le A_N \le 10^ 5$

Output Format

輸出一行，包含一個正整數，代表二進位轉換後的字串的最短長度。

Sample Input 1

4
1 1 2 3

Sample Output 1

13

Sample Input 2

5
4 4 8 8 16

Sample Output 2

88

Hints

Problem Source

Subtasks

No. Testdata Range Constraints Score
1 0~1 範例測資 0
2 0~19 無額外限制 100

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 1000 524288 65536 1 2
1 1000 524288 65536 1 2
2 1000 524288 65536 2
3 1000 524288 65536 2
4 1000 524288 65536 2
5 1000 524288 65536 2
6 1000 524288 65536 2
7 1000 524288 65536 2
8 1000 524288 65536 2
9 1000 524288 65536 2
10 1000 524288 65536 2
11 1000 524288 65536 2
12 1000 524288 65536 2
13 1000 524288 65536 2
14 1000 524288 65536 2
15 1000 524288 65536 2
16 1000 524288 65536 2
17 1000 524288 65536 2
18 1000 524288 65536 2
19 1000 524288 65536 2
Submit
Back to Top