https://www.nowcoder.com/practice/162753046d5f47c7aac01a5b2fcda155?tpId=67&tqId=29635&tPage=0&ru=/kaoyan/retest/1005&qru=/ta/bupt-kaoyan/question-ranking

题目描述

哈夫曼树，第一行输入一个数n，表示叶结点的个数。需要用这些叶结点生成哈夫曼树，根据哈夫曼树的概念，这些结点有权值，即weight，题目需要输出所有结点的值与权值的乘积之和。

输入描述:

输入有多组数据。 每组第一行输入一个数n，接着输入n个叶节点（叶节点权值不超过100，2<=n<=1000）。

输出描述:

输出权值。

示例1

输入

5  1 2 2 5 9 哈夫曼树结点的weight有一个定理：最小带权路径长度为非叶子结点的和 ，即WPL= 19 + 10 +5 +3=37

#include
          
           #include
           
            #include
            
             #include
             
              #include
              
               using namespace std;struct numfloor{    int data;    int used;} b[10002];int donser(const void *a,const void *b){    return ((struct numfloor*)b)->data-((struct numfloor*)a)->data;}int main(){    int num;    while(scanf("%d",&num)!=EOF)    {        int number=num,i=1,a[10002];        while(i<=num)        {            scanf("%d",&b[i].data);            b[i].used=2;            i++;        }        qsort(b+1,num,sizeof(numfloor),donser);        while(num>0)        {            int temp1=b[num].data;            num--;            int temp2=b[num].data;            b[num].data=temp1+temp2;            b[num].used=1;            a[num]=b[num].data;            qsort(b+1,num,sizeof(numfloor),donser);        }        int sum=0;        for(int i=1; i
              
             
            
           
          

 

输出

37