wustoj (创建一棵哈夫曼树)

た入场券 2022-06-04 01:45 174阅读 0赞

问题描述:

老康维修牧场的一段栅栏需要N（1≤N≤200）根木头，每根木头的长度为整数Li（1≤N≤50）.于是他购买了一根非常长的能锯成N段的木头（即该木头的长度是所有Li的总和）。忽略锯木头的时候产生的锯末而造成的长度损耗。

老康自己没有锯子，需要想邻居老王借锯子。邻居老王是一个非常抠的人，他需要向老康收取锯子的损耗费（不清楚他怎么想出来的）。每锯一次的费用与所锯木头的长度成正比（假定比例系数为1）。

现在需要你来帮老康算一算，他锯成N跟木头（需要锯N-1次）所需的最小费用是多少。

输入

包含多组测试数据。每组测试数据包含一行。每行的第一个整数为N，后面接N个整数（每根木头的长度）。整数之间用空格隔开。

输出

锯N-1次需要支付的最小费用。

样例

输入

3 8 5 8

4 7 5 2 4

输出

题目分析:很明显就是利用哈夫曼数的思想，先解决短的，依次增加。其实利用这个思想可以写出很简单的代码，但是是数据结构的作业，还是有必要建一棵哈夫曼树的！

代码如下:

#include<iostream>
    #include<cstdio>
    #include<cmath>
    #include<algorithm>
    #include<cstring>
    #include<vector>
    #include<queue>
    using namespace std;
    
    const int maxn=200;
    int n,l,ans;
    struct note
    {
        int val;
        struct note* lchild;
        struct note* rchild;
        bool operator <(const struct note &a) const {
            return val>a.val;
        }
    }*Tree;
    priority_queue<struct note> que;
    
    void dfs(struct note *root,int step)
    {
        struct note *L,*R;
        L=root->lchild;
        R=root->rchild;
        if (L==NULL&&R==NULL) {
            ans+=step*(root->val);
            return ;
        }
        if (L!=NULL) dfs(L,step+1);
        if (R!=NULL) dfs(R,step+1);
    }
    int main()
    {
        while (scanf("%d",&n)!=EOF) {
            for (int i=0;i<n;i++) {
                struct note a;
                scanf("%d",&a.val);
                a.lchild=a.rchild=NULL;
                que.push(a);
            }
            ans=0;
            while (que.size()>1) {
                struct note *a,*b,*c;
                a=new struct note();
                b=new struct note();
                c=new struct note();
                *a=que.top();que.pop();
                *b=que.top();que.pop();
                c->val=a->val+b->val;
                c->lchild=a;
                c->rchild=b;
                que.push(*c);
            }//创建一棵哈夫曼树
            struct note head=que.top();
            que.pop();
            Tree=&head;
            dfs(Tree,0);//求树的带权路径长度
            printf("%d\n",ans);
        }
        return 0;
    }