1700 問題 A: 數(shù)據(jù)結(jié)構(gòu)-自底向上的赫夫曼編碼
時間限制: 1s
內(nèi)存限制: 32MB 提交: 1722 解決: 607
題目描述
在通訊領域，經(jīng)常需要將需要傳送的文字轉(zhuǎn)換成由二進制字符組成的字符串。在實際應用中，由于總是希望被傳送的內(nèi)容總長盡可能的短，如果對每個字符設計長度不等的編碼，且讓內(nèi)容中出現(xiàn)次數(shù)較多的字符采用盡可能短的編碼，則整個內(nèi)容的總長便可以減少。另外，需要保證任何一個字符的編碼都不是另一個字符的編碼前綴，這種編碼成為前綴編碼。
而赫夫曼編碼就是一種二進制前綴編碼，其從葉子到根（自底向上）逆向求出每個字符的算法可以表示如下：
在本題中，讀入n個字符所對應的權(quán)值，生成赫夫曼編碼，并依次輸出計算出的每一個赫夫曼編碼。
輸入
輸入的第一行包含一個正整數(shù)n，表示共有n個字符需要編碼。其中n不超過100。
第二行中有n個用空格隔開的正整數(shù)，分別表示n個字符的權(quán)值。
輸出
共n行，每行一個字符串，表示對應字符的赫夫曼編碼。
樣例輸入
8 5 29 7 8 14 23 3 11
樣例輸出
0110 10 1110 1111 110 00 0111 010
提示
比賽公告
111111111111111111111開始比賽
111111111111111111111開始比賽
111111111111111111111開始比賽
111111111111111111111開始比賽
111111111111111111111開始比賽
111111111111111111111開始比賽
111111111111111111111開始比賽
111111111111111111111開始比賽
111111111111111111111開始比賽
111111111111111111111開始比賽