线性时间Huffman算法

「爱情、让人受尽委屈。」 2022-08-18 02:26 133阅读 0赞

## 线性时间Huffman算法 ##

####  ####

##### Time Limit: 1000ms Memory limit: 65536K 有疑问？点这里^\_^ #####

## 题目描述 ##

在一个操场的四周摆放着n 堆石子。每堆的石子数不超过10\*n。现要将石子有次序地合并成一堆。规定每次只能选2 堆石子合并成新的一堆，合并的费用为新的一堆的石子数。  
试设计一个线性时间算法，计算出将n堆石子合并成一堆的最小总费用。  
对于给定n堆石子,计算合并成一堆的最小总费用。

## 输入 ##

输入数据的第1 行是正整数n，表示有n堆石子。第2 行有n个数，分别表示每堆石子的个数。n≤100000。

## 输出 ##

将计算出的最小总费用输出。

## 示例输入 ##

6
    45 13 12 16 9 5

## 示例输出 ##

224

#include <stdio.h>  
    #include <queue>  
      
    using namespace std;  
      
    struct cmp  
    {  
        bool operator ()(int a,int b)  
        {  
            return b < a;  
        }  
    };  
      
    int main()  
    {  
        int k,i,n,m,sum;  
        priority_queue <int,vector<int>,cmp> q;  
        scanf("%d",&n);  
      
            sum = 0;  
            while(!q.empty())  
                q.pop();  
            for(i = 0; i < n; i++)  
            {  
                scanf("%d",&k);  
                q.push(k);  
            }  
            while(!q.empty())  
            {  
                k = q.top();  
                q.pop();  
                m = q.top();  
                q.pop();  
                sum += (k + m);  
                if(!q.empty())  
                    q.push(k + m);  
                else  
                {  
                    printf("%d\n",sum);  
                    break;  
                }  
            }  
        return 0;  
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，133人围观）

还没有评论，来说两句吧...

相关阅读

相关亚线性时间算法求连通分量

要求 ![在这里插入图片描述][dd0ccf27d8874022b9aab3a6a96f7c07.png]自己给出ϵ的值并带入计算简述算法过程先用一个队列，建

╰半夏微凉°/ 2023年10月06日 21:36/ 0 赞/ 37 阅读

相关 Huffman 编码压缩算法

前两天发布那个[rsync算法][rsync]后，想看看数据压缩的算法，知道一个经典的压缩算法Huffman算法。相信大家应该听说过 [David Huffman][] 和他的

女爷i/ 2022年09月24日 15:29/ 0 赞/ 188 阅读

相关线性时间Huffman算法

线性时间Huffman算法 Time Limit: 1000ms Memory limit: 65536K 有疑问？点这里^\_^ 题目描述在一个操

「爱情、让人受尽委屈。」/ 2022年08月18日 02:26/ 0 赞/ 134 阅读

相关线性时间排序

说明：比较排序算法的复杂度下界是 O(nlog(n)) 一、计数排序（复杂度是O(n)）计数排序要求被排序元素都是整数型变量，即元素能用数组的指标表示（1）统计个

待我称王封你为后i/ 2022年06月09日 14:39/ 0 赞/ 158 阅读

相关算法导论第8章线性时间排序答案

一、概念 1.比较排序比较排序是指通过输入元素间的比较来确定各元素次序的排序算法。任何比较排序在最坏情况下都要用O(nlgn)次比较来进行排序合并排序和堆

怼烎@/ 2022年05月14日 03:26/ 0 赞/ 237 阅读

相关趣学算法-贪心算法： Huffman编码

> Huffman编码的原理：以字符的使用频率作为权构建一棵哈夫曼树，然后利用哈夫曼树对字符进行编码。构造一棵哈夫曼树，是将所要编码的字符作为叶子结点，该字符在文件中的使用

痛定思痛。/ 2022年05月10日 12:33/ 0 赞/ 261 阅读

相关线性时间的排序算法

线性时间的排序算法计数排序算法思路算法实现基数排序算法思路算法实现桶排序

缺乏、安全感/ 2022年04月23日 07:00/ 0 赞/ 169 阅读

相关线性时间排序总结

[2019独角兽企业重金招聘Python工程师标准>>> ][2019_Python_] ![hot3.png][] 计数排序计数排序（counting sort）的

向右看齐/ 2022年01月13日 12:15/ 0 赞/ 206 阅读

相关 [转载]Huffman编码压缩算法

转自http://coolshell.cn/articles/7459.html 前两天发布那个[rsync算法][rsync]后，想看看数据压缩的算法，知道一个经典的压缩算

爱被打了一巴掌/ 2022年01月10日 05:29/ 0 赞/ 241 阅读

相关数据结构和算法——Huffman树和Huffman编码

Huffman树是一种特殊结构的二叉树，由Huffman树设计的二进制前缀编码，也称为Huffman编码在通信领域有着广泛的应用。在word2vec模型中，在构建层次Softm

比眉伴天荒/ 2021年09月18日 09:26/ 0 赞/ 365 阅读