藍橋杯 VIP 基礎練習 Huffuman樹

 基礎練習 Huffuman樹   時間限制：1.0s   記憶體限制：512.0MB         問題描述 　　Huffman樹在編碼中有着廣泛的應用。在這裡，我們隻關心Huffman樹的構造過程。

　　給出一列數{p i}={p 0, p 1, …, p n -1}，用這列數構造Huffman樹的過程如下：

　　1. 找到{p i}中最小的兩個數，設為p a和p b，将p a和p b從{p i}中删除掉，然後将它們的和加入到{p i}中。這個過程的費用記為p a + p b。

　　2. 重複步驟1，直到{p i}中隻剩下一個數。

　　在上面的操作過程中，把所有的費用相加，就得到了構造Huffman樹的總費用。

　　本題任務：對于給定的一個數列，現在請你求出用該數列構造Huffman樹的總費用。

　　例如，對于數列{p i}={5, 3, 8, 2, 9}，Huffman樹的構造過程如下：

　　1. 找到{5, 3, 8, 2, 9}中最小的兩個數，分别是2和3，從{p i}中删除它們并将和5加入，得到{5, 8, 9, 5}，費用為5。

　　2. 找到{5, 8, 9, 5}中最小的兩個數，分别是5和5，從{p i}中删除它們并将和10加入，得到{8, 9, 10}，費用為10。

　　3. 找到{8, 9, 10}中最小的兩個數，分别是8和9，從{p i}中删除它們并将和17加入，得到{10, 17}，費用為17。

　　4. 找到{10, 17}中最小的兩個數，分别是10和17，從{p i}中删除它們并将和27加入，得到{27}，費用為27。

　　5. 現在，數列中隻剩下一個數27，構造過程結束，總費用為5+10+17+27=59。 輸入格式 　　輸入的第一行包含一個正整數n（n<=100）。

　　接下來是n個正整數，表示p 0, p 1, …, p n -1，每個數不超過1000。 輸出格式 　　輸出用這些數構造Huffman樹的總費用。 樣例輸入 5

5 3 8 2 9 樣例輸出 59 若果大家學過資料結構或者離散數學，因該對這種算法并不陌生，題目中就是要求計算這棵哈弗曼樹的每一個分支點的權值之和，實際上就是這棵樹的權，分析可知，這個算法涉及到排序以及集合的相關運算，自然會想到STL中的set，不過，因為集合中可能會出現相同的元素，是以應該使用multiset，資料操作主要有彈出，插入，删除，彈出元素需要使用疊代器，it指向begin()的位置，然後*it擷取值，最後erase(it)删除這個元素，每次彈出兩個元素，并将這兩個元素的和插入到容器中，将兩個元素的和累加到sum中去，如果最終容器中隻有一個元素，運算停止。

#include <iostream>
#include <cmath>
#include <stdio.h>
#include <string>
#include <cstring>
#include <map>
#include <set>
#include <vector>
#include <stack>
#include <queue>
#include <iomanip>
#include <algorithm>
#include <memory.h>
using namespace std;
multiset<int> s;
multiset<int>::iterator it;
int sum;

void init()
{
    s.clear();
    sum=0;
}
void operate()
{
    int a,b;
    while(s.size()>1)
    {
        it=s.begin();
        a=*it;
        s.erase(it++);
        b=*it;
        s.erase(it);
        s.insert(a+b);
        sum+=(a+b);
    }
    it=s.begin();
}


int main()
{
    int i,n,num;
    cin>>n;
    for(i=0;i<n;i++)
    {
        cin>>num;
        s.insert(num);
    }
    operate();
    cout<<sum<<endl;
    return 0;
}