POJ 3253 Fence Repair【哈夫曼树】

痛定思痛。 2022-10-16 10:29 23阅读 0赞

**哈夫曼树**

同

[https://liyunhao.blog.csdn.net/article/details/117094052][https_liyunhao.blog.csdn.net_article_details_117094052]

注意结果要用long long 因为Li可能被加和多次 N\*max(Li)不不是求和的最大值

#include <iostream>
    #include <queue>
    #include <vector>
    #include <algorithm>
    
    using namespace std;
    
    #define debug(x) cout<<#x<<": "<<(x)<<endl;
    #pragma warning(disable:4996)
    
    
    
    int main()
    { 
        //freopen("../in2.txt","r",stdin);
    
        priority_queue< int, vector<int>, greater<int> > q;
        int N;
        cin >> N;
        for (int i = 0; i < N; ++i) { 
            int t;
            cin >> t;
            q.push(t);
        }
        long long int ret = 0;
        while (q.size() > 1) { 
            int a = q.top();
            q.pop();
            int b = q.top();
            q.pop();
            q.push(a + b);
            ret += a + b;
        }
        
        cout << ret << endl;
        
        return 0;
    }

![在这里插入图片描述][20210529220846895.png]

[https_liyunhao.blog.csdn.net_article_details_117094052]: https://liyunhao.blog.csdn.net/article/details/117094052
[20210529220846895.png]: /images/20221014/c852df63614c4ce5a6bb66a279a98396.png

发表评论取消回复

表情：

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

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

相关阅读

相关 POJ 3253 Fence Repair 贪心优先级队列

Fence Repair <table> <tbody> <tr> <td><strong>Time Limit:</strong> 2000MS

痛定思痛。/ 2023年07月12日 05:05/ 0 赞/ 6 阅读

相关 POJ 3253 Fence Repair【哈夫曼树】

哈夫曼树同 [https://liyunhao.blog.csdn.net/article/details/117094052][https_liyunhao.blog.

痛定思痛。/ 2022年10月16日 10:29/ 0 赞/ 24 阅读

相关哈夫曼树、哈夫曼编码详解

哈夫曼树介绍 hello，大家好，我是bigsai。本以为哈夫曼树、哈夫曼编码很难，结果很容易嘛！哈夫曼树、哈夫曼编码很多人可能听过，但是可能并没有认真学习了解，今天

╰+哭是因爲堅強的太久メ/ 2022年10月07日 08:54/ 0 赞/ 298 阅读

相关 Fence Repair （哈弗曼树+快排） poj 3253 c++

Fence Repair <table> <tbody> <tr> <td><strong>Time Limit:</strong> 2000MS

悠悠/ 2022年08月10日 13:53/ 0 赞/ 128 阅读

相关哈夫曼树与哈夫曼编码

在一般的数据结构的书中，树的那章后面，著者一般都会介绍一下哈夫曼(HUFFMAN) 树和哈夫曼编码。哈夫曼编码是哈夫曼树的一个应用。哈夫曼编码应用广泛，如 JPEG中就应用

曾经终败给现在/ 2022年07月30日 19:21/ 0 赞/ 294 阅读

相关哈夫曼树和哈夫曼编码

哈夫曼树给定n个权值作为n的叶子结点，构造一棵二叉树，若带权路径长度达到最小，称这样的二叉树为最优二叉树，也称为哈夫曼树(Huffman Tree)。哈夫曼树是带权路径

快来打我*/ 2022年07月18日 01:23/ 0 赞/ 271 阅读

相关 POJ 3253-Fence Repair（哈夫曼树-最小值优先队列）

Fence Repair <table> <tbody> <tr> <td><strong>Time Limit:</strong> 2000MS

墨蓝/ 2022年07月11日 13:14/ 0 赞/ 143 阅读

相关 POJ 3253 Fence Repair（哈夫曼树+优先队列）

Farmer John wants to repair a small length of the fence around the pasture. He measures

快来打我*/ 2022年06月09日 00:16/ 0 赞/ 158 阅读

相关 Fence Repair POJ - 3253 (贪心+HuffmanTree)

Farmer John wants to repair a small length of the fence around the pasture. He measures

末蓝、/ 2022年03月09日 09:06/ 0 赞/ 201 阅读

相关 POJ 3253 Fence Repair(小顶堆的应用)

Fence Repair <table> <tbody> <tr> <td> <p><strong>Time Limit:</strong> 20

忘是亡心i/ 2021年11月02日 06:32/ 0 赞/ 224 阅读