• 热门专题

poj3253FenceRepair(优先队列+哈夫曼树)

作者:  发布日期:2014-08-04 20:19:16
Tag标签:队列  
  • 题目地址:POJ 3253

    哈夫曼树的结构就是一个二叉树,每一个父节点都是两个子节点的和。这个题就是可以从子节点向根节点推。

    每次选择两个最小的进行合并。将合并后的值继续加进优先队列中。直至还剩下一个元素为止。

    代码如下:

    #include <iostream>
    #include <stdio.h>
    #include <string.h>
    #include <stdlib.h>
    #include <math.h>
    #include <ctype.h>
    #include <queue>
    #include <map>
    #include<algorithm>
    
    using namespace std;
    struct node
    {
        __int64 x;
        bool operator <(const node &a) const
        {
            return x>a.x;
        }
    };
    int main()
    {
        __int64 n, i, j, x, ans;
        while(scanf("%I64d",&n)!=EOF)
        {
            ans=0;
            priority_queue<node>q;
            node p, f1, f2, s;
            for(i=0; i<n; i++)
            {
                scanf("%I64d",&p.x);
                q.push(p);
            }
            while(!q.empty())
            {
                f1=q.top();
                q.pop();
                if(q.empty())
                {
                    break;
                }
                f2=q.top();
                q.pop();
                s.x=f1.x+f2.x;
                q.push(s);
                //printf("%d  %d\n",f1.x,f2.x);
                ans+=s.x;
            }
            printf("%I64d\n",ans);
        }
        return 0;
    }
    


About IT165 - 广告服务 - 隐私声明 - 版权申明 - 免责条款 - 网站地图 - 网友投稿 - 联系方式
本站内容来自于互联网,仅供用于网络技术学习,学习中请遵循相关法律法规