HDU 1053 Entropy(贪心)

痛定思痛。 2022-06-03 00:12 158阅读 0赞

这道题是哈弗曼树+贪心；

[哈夫曼树][Link 1]：

[哈夫曼树][Link 1]又称最优[二叉树][Link 2]，是一种带权路径长度最短的二叉树。所谓树的带权路径长度，就是树中所有的[叶结点][Link 3]的[权值][Link 4]乘上其到[根结点][Link 5]的路径长度（若根结点为0层，叶结点到根结点的路径长度为叶结点的层数）。树的带权路径长度记为WPL=(W1\*L1+W2\*L2+W3\*L3+...+Wn\*Ln)，N个权值Wi(i=1,2,...n)构成一棵有N个叶结点的二叉树，相应的叶结点的路径长度为Li(i=1,2,...n)。可以证明哈夫曼树的[WPL][]是最小的。

科普就到这了。如果不是很清楚哈弗曼树的话建议自行百度。因为有些好的解答不能转载的原因就不贴链接了。

#include <stdio.h>
    #include <math.h>
    #include <string.h>
    #include <algorithm>
    using namespace std;
    char a[100005];
    int num[55];
    int cmp(int a,int b)
    {
        return a>b;
    } 
    //排序,从大到小； 
    int main(int argc, char *argv[])
    {
        int n;
        int i,j;
        double wan1,wan2;
        while(~scanf("%s",a)&&strcmp(a,"END")!=0)//开始输入 
        {
            wan1=wan2=0;//wan1代表ascll编码，wan2代表haffman编码
            memset(num,0,sizeof(num));
            for(i=0;a[i]!=0;i++)
            {
                if(a[i]<='Z')
                    num[a[i]-'A']++;//统计字符串里的所有字母的总和 
                else
                    num[26]++;//下划线的总和    
            }            
            sort(num,num+27,cmp);//排序 
            wan1=8*i;//ascll编码
            n=27;
            while(num[n-1]==0)//去掉为数值为零的数组 
                n--;
            while(n>1)//开始构造haffman树运算 
            {
                int min1=0,min2=1;//用来取哈弗曼树权值最小的两位 
                if(num[min1]>num[min2])
                {
                    int t=min1;
                    min1=min2;
                    min2=t;
                }
                for(i=2;i<n;i++)
                {
                    if(num[min1]>num[i])
                    {
                        min2=min1;
                        min1=i;
                    }
                    else if(num[min2]>num[i])
                        min2=i;        
                }//排完序后min1和min2会取到最小值 
                wan2+=num[min1]+num[min2];//取得两个最小的数构成的权值 
                if(min1==n-1)
                {
                    int t=min1;
                    min1=min2;
                    min2=t;
                } 
                num[min1]+=num[min2];//新树的权值  1+2=3； 
                num[min2]=num[n-1];
                n--;
            }
            if(wan2)
                printf("%.lf %.lf %.1lf\n",wan1,wan2,1.0*wan1/wan2);
            else 
                printf("%.lf %.lf 8.0\n",wan1,wan1/8);
        }    
        return 0;
    }

//Start-ZJ

//2017/12/12/19:35

[Link 1]: https://baike.baidu.com/item/%E5%93%88%E5%A4%AB%E6%9B%BC%E6%A0%91
[Link 2]: https://baike.baidu.com/item/%E4%BA%8C%E5%8F%89%E6%A0%91
[Link 3]: https://baike.baidu.com/item/%E5%8F%B6%E7%BB%93%E7%82%B9/9795627
[Link 4]: https://baike.baidu.com/item/%E6%9D%83%E5%80%BC/170585
[Link 5]: https://baike.baidu.com/item/%E6%A0%B9%E7%BB%93%E7%82%B9/9795570
[WPL]: https://baike.baidu.com/item/WPL/10089687