哈夫曼编码和哈夫曼树

哈夫曼编码常见应用

例题：poj3253
锯木头，比如要锯的木头长度为10，那么花费10元，问截成8 5 8最少需要多少钱？——排序、从最小的两两加起来；就是：5 8 8；5+8=13；13+8=21；故花费为13+21=34；

#include <iostream>
#include <queue>
using namespace std;
int main()
{
    priority_queue<int,vector<int>,greater<int> > q;//注意
    int n;cin>>n;
    for(int i=0;i<n;i++)
    {
        int tmp;cin>>tmp;
        q.push(tmp);
    }
    long long ans=0;
    while(!q.empty())
    {
        int a=q.top();q.pop();
        if(q.empty()) break;
        int b=q.top();q.pop();
        int newnum=a+b;
        ans+=newnum;
        q.push(newnum);
    }
    cout<<ans<<endl;
    return 0;
}

提升题：二分+哈夫曼树 hdu5884

#include<stdio.h>
#include<iostream>
#include<queue>
#include <algorithm>
using namespace std;
int n,m;
long long t;
int a[100010],front_sum[100010];
priority_queue<int,vector<int>,greater<int> >q;
bool huffman(int k)
{
    long long sum=0;
    while(!q.empty()) q.pop();
    int mo=(n-1)%(k-1);
    if(mo)
    {
        mo+=1;
        sum+=front_sum[mo];
        q.push(sum);

    }
    for(int i=mo; i<n; i++)
    {
        q.push(a[i]);
    }
    int tmp=0;
    int up = (n - 1) / (k - 1);
    for(int i =  0 ; i < up ; i ++)
    {
        tmp=0;
        for(int j=0; j<k; j++)
        {
            tmp+=q.top();
            q.pop();
        }
        q.push(tmp);
        sum+=tmp;

    }
    if(sum<=m) return 1;
    else return 0;
}
int main()
{

    scanf("%d",&t);
    while(t--)
    {
        scanf("%d%d",&n,&m);
        front_sum[0]=0;
        for(int i=0;i<n;i++)
             scanf("%d",&a[i]);
        sort(a , a+n);
        for(int i=1;i<=n;i++)
             front_sum[i]=front_sum[i-1]+a[i-1];
        int h=n;
        int l=2;
        int mid;
        while(h>l)
        {
            mid=(h+l)/2;

            if(huffman(mid))
                h=mid;
            else
                l=mid+1;
        }
        if(n <= 1) h = 1;
       printf("%d\n",h);
    }
    return 0;
}