【藍橋杯】BASIC-28 Huffman樹

2019 年 11 月 13 日
筆記

本文鏈接：https://blog.csdn.net/weixin_42449444/article/details/102994042

題目描述：

Huffman樹在編碼中有著廣泛的應用。在這裡，我們只關心Huffman樹的構造過程。給出一列數{pi}={p0, p1, …, pn-1}，用這列數構造Huffman樹的過程如下： 1. 找到{pi}中最小的兩個數，設為pa和pb，將pa和pb從{pi}中刪除掉，然後將它們的和加入到{pi}中。這個過程的費用記為pa + pb。 2. 重複步驟1，直到{pi}中只剩下一個數。在上面的操作過程中，把所有的費用相加，就得到了構造Huffman樹的總費用。本題任務：對於給定的一個數列，現在請你求出用該數列構造Huffman樹的總費用。例如，對於數列{pi}={5, 3, 8, 2, 9}，Huffman樹的構造過程如下： 1. 找到{5, 3, 8, 2, 9}中最小的兩個數，分別是2和3，從{pi}中刪除它們並將和5加入，得到{5, 8, 9, 5}，費用為5。 2. 找到{5, 8, 9, 5}中最小的兩個數，分別是5和5，從{pi}中刪除它們並將和10加入，得到{8, 9, 10}，費用為10。 3. 找到{8, 9, 10}中最小的兩個數，分別是8和9，從{pi}中刪除它們並將和17加入，得到{10, 17}，費用為17。 4. 找到{10, 17}中最小的兩個數，分別是10和17，從{pi}中刪除它們並將和27加入，得到{27}，費用為27。 5. 現在，數列中只剩下一個數27，構造過程結束，總費用為5+10+17+27=59。

輸入描述：

輸入的第一行包含一個正整數n（n< =100）。接下來是n個正整數，表示p0, p1, …, pn-1，每個數不超過1000。

輸出描述：

輸出用這些數構造Huffman樹的總費用。

輸入樣例：

5  5 3 8 2 9

輸出樣例：

解題思路：

我是採用一個升序排列的優先隊列來進行求解的，用sum來記錄構造Huffman樹的總花費。先將所有數放入優先隊列中，不斷地取出優先隊列中最小的倆個值，再將它們的累加和放入隊列中，同時sum不斷地累加它們的累加和，直到隊列中僅剩一個元素為止。寫完這題後靈感一現，發現前幾天演算法分析與設計實驗課的那道題最優合併問題也可以用優先隊列來進行求解。

AC程式碼：

#include <bits/stdc++.h>  using namespace std;  #define Up(i,a,b) for(int i = a; i <= b; i++)    int main()  {      ios::sync_with_stdio(false);      cin.tie(0),cout.tie(0);      priority_queue<int,vector<int>,greater<int> > pq;    //升序排列的優先隊列      int n;      cin >> n;      Up(i,1,n)      {          int _;          cin >> _;          pq.push(_);      }      int sum = 0;      while(pq.size() != 1)      {          int _ = pq.top();          pq.pop();          _ += pq.top();          pq.pop();          pq.push(_);          sum += _;      }      cout << sum << endl;      return 0;  }