a821. CPE：Variable Radix Huffman Encoding (UVa 240)

困難CPE

時間限制 2000 ms ・ 記憶體限制 256 MB

題目描述

請依指定的霍夫曼編碼規則，把前 N 個大寫英文字母 A、B、… 編碼為由數字 0 至 R − 1 組成的字串，使依出現頻率加權的平均碼長最短。 一開始每個字母各是一個項目，權重為其頻率。每一步挑選權重最小的 R 個項目，依權重由小到大分別配上數字 0、1、…、R − 1，再把它們合併成一個新項目，新權重等於各項目權重總和。 權重相同時，內含字母中字母順序最前者優先。合併項目同樣以內含的最前字母比較。各字母的最終碼字是從最後形成的根向下走到該字母時，沿路配上的數字；也就是依合併發生順序取得的數字必須反向串接。 當 R > 2 時，要先補入適量頻率為 0 的虛構字母，使每次都能合併 R 個項目，最後也恰好剩下 R 個再合併成根。補入最少的必要數量即可，使總項目數形如 k(R − 1) + R。所有虛構字母在比較順序上都排在真實字母之後，且不輸出其編碼。

輸入格式

每筆一行：R N f₁ f₂ … fₙ。2 ≤ R ≤ 10、2 ≤ N ≤ 26、1 ≤ fᵢ ≤ 999。fᵢ 為第 i 個大寫字母的頻率。以 R = 0 結束。

輸出格式

每筆先輸出 Set k; average length a，其中 k 從 1 起編號，a 為 Σ(fᵢ × 碼長ᵢ) / Σfᵢ，四捨五入並固定兩位小數。 接著依字母順序輸出 N 行，每行先四個空白，再輸出「A: code」這種格式。每筆後都印一個空白行。

題目來源：UVa 240 — Variable Radix Huffman Encoding。 原題：https://onlinejudge.org/external/2/240.pdf

出題者： Chatgpt聯絡出題者

範例測資

範例輸入 1

2 5 5 10 20 25 40
2 5 4 2 2 1 1
3 7 20 5 8 5 12 6 9
4 6 10 23 18 25 9 12
0

範例輸出 1

Set 1; average length 2.10
    A: 1100
    B: 1101
    C: 111
    D: 10
    E: 0

Set 2; average length 2.20
    A: 11
    B: 00
    C: 01
    D: 100
    E: 101

Set 3; average length 1.69
    A: 1
    B: 00
    C: 20
    D: 01
    E: 22
    F: 02
    G: 21

Set 4; average length 1.32
    A: 32
    B: 1
    C: 0
    D: 2
    E: 31
    F: 33
請先登入後再提交程式碼

討論與題解

載入討論區…

更多