哈夫曼压缩编码

问题描述

求哈夫曼编码的最小编码长度。

输入格式

输入的第一行包含一个整数n，表示单词的数量。
第二行包含n个整数，用空格分隔，分别表示a1, a2, …, an出现的频率，即t1,t2, …, tn。请注意a1, a2, …, an具体是什么单词并不影响本题的解，所以没有输入a1, a2, …, an。

输出格式

输出一个整数，表示文字经过编码后的长度L的最小值。

输入样例

5
1 3 4 5 2

输出样例

33

代码实现

#include<iostream>
#include<algorithm>
#include<vector>

using namespace std;

const int N = 1000;
vector<int> v;
void Print(vector<int> v){
    for(vector<int> :: iterator it = v.begin();it != v.end(); it++){
        cout<<*it<<' ';
    }
    cout<<endl;
}
int main()
{
    int n,x,sum = 0;
    cin>>n;
    for(int i = 0; i < n; i++){
        cin>>x;
        v.push_back(x);
    }
    sort(v.begin(),v.end(),less<int>());

    for(int i = 0; i < v.size()-1;){
        v[i+1] += v[i];
        sum += v[i+1];
        Print(v);
        v.erase(v.begin());
        Print(v);
        sort(v.begin(),v.end(),less<int>());
    }
    cout<<endl;
    cout<<sum;
    return 0;
}

运行结果

5
1 3 4 5 2
1 3 3 4 5
3 3 4 5
3 6 4 5
6 4 5
4 9 6
9 6
6 15
15

33