POJ 3253 Fence Repair【哈夫曼树】

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

哈夫曼树

同

https://liyunhao.blog.csdn.net/article/details/117094052

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

  1. #include <iostream>
  2. #include <queue>
  3. #include <vector>
  4. #include <algorithm>
  6. using namespace std;
  8. #define debug(x) cout<<#x<<": "<<(x)<<endl;
  9. #pragma warning(disable:4996)
  13. int main()
  14. { 
  15.     //freopen("../in2.txt","r",stdin);
  17.     priority_queue< int, vector<int>, greater<int> > q;
  18.     int N;
  19.     cin >> N;
  20.     for (int i = 0; i < N; ++i) { 
  21.         int t;
  22.         cin >> t;
  23.         q.push(t);
  24.     }
  25.     long long int ret = 0;
  26.     while (q.size() > 1) { 
  27.         int a = q.top();
  28.         q.pop();
  29.         int b = q.top();
  30.         q.pop();
  31.         q.push(a + b);
  32.         ret += a + b;
  33.     }
  35.     cout << ret << endl;
  37.     return 0;
  38. }

在这里插入图片描述

发表评论

表情：
评论列表 （有 0 条评论，104人围观）

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

相关阅读

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

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

    快来打我*快来打我*/ 0 赞/ 377 阅读