首页 > 代码库 > 【uva 10954】Add All（算法效率+Huffman编码+优先队列）
【uva 10954】Add All（算法效率+Huffman编码+优先队列）
题意：有N个数，每次选2个数合并为1个数，操作的开销就是这个新的数。直到只剩下1个数，问最小总开销。
解法：合并的操作可以转化为二叉树上的操作【建模】，每次选两棵根树合并成一棵新树，新树的根权值等于两棵合并前树的根权值和（也与Huffman编码的建立过程类似，选权值最小的两棵树）。
这样总开销就是除了叶子结点的权值和 =》 每个叶子结点的权值*层数（根节点层数为0）之和 =》 WPL（树的所有叶子节点的带权路径长度之和，即该节点到根节点路径长度与节点上权的乘积之和）。
而Huffman树就是带权路径长度WPL最短的二叉树，又称最优二叉树。这样建树WPL就最短的原因很明显了，由于n个父亲节点的哈夫曼树含有2n-1个节点，没有度为1的节点，那么叶子结点数确定了，每层的结点数也确定了，那么权值大的点肯定深度越小越好，权值小的点肯定相对来说深度越大越好，这样建树的WPL就一定是最小的。
于是我们用优先队列来做每次合并权值最小的2个数的操作。
1 #include<cstdio> 2 #include<cstdlib> 3 #include<cstring> 4 #include<algorithm> 5 #include<iostream> 6 #include<queue> 7 using namespace std; 8 const int N=5010,D=(int)1e5+10; 9 10 priority_queue<int,vector<int>,greater<int> > q;//使优先队列从小到大排列；不能>>连起来，中间要有空格11 int main()12 {13 int n,x,y,h,i;14 while (~scanf("%d",&n))15 {16 if (!n) break;17 while (!q.empty()) q.pop();18 for (i=1;i<=n;i++) scanf("%d",&x),q.push(x);19 h=0;20 for (i=1;i<n;i++)21 {22 x=q.top(),q.pop();23 y=q.top(),q.pop();24 q.push(x+y), h+=x+y;25 }26 printf("%d\n",h);27 }28 return 0;29 }
【uva 10954】Add All（算法效率+Huffman编码+优先队列）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。