Huffman树、贪心、荷马史诗
题目链接:https://vjudge.net/contest/373557#problem/I
题目大意:求 重新编码后的 最短长度 和 重新编码后的 最长字符串的长度
数据结构刚学了Huffman树,比赛就考到了Huffman编码,在这里整理一下。
Huffman树是最优二叉树,这道题相当于最优k叉树,但是又有些不同。
不会Huffman树的可以从百度搜索,这里就不具体讲了。
Huffman树是在队列中挑出最小的两个权值组成一新节点,并放入队列中。
在这道题里面,并不是二进制,而是K进制,所以想要用到Huffman树,必须要满足(n-1)%(k-1)==0,这个条件的意思就是:最后合并的时候肯定能满足只剩k个节点,刚好能合并成最后一个节点。(不行的话,可以自己举几个例子试试)
如果不满足这个条件的话就要把{0,0}代替节点输进去。
这道题还要用到优先队列,我有一条龙服务,不会优先队列的,我博客里面有关于优先队列的单独一篇,下面给链接:https://blog.nowcoder.net/n/ad8e1df876064b0a8a3034b7df74f35d
这里优先队列的应用就是把节点中权值小的放到前面,如果权值一样的话,就把深度小的放到前面。
用一个while循环,直到优先队列中只剩下最后一个元素的时候,结束循环。(这里要注意不是优先队列为空的时候,是优先队列大小为1的时候停止循环)
循环里面就是每k个为一组,把长度值加起来并加到要输出的最终长度值上,把三个的深度求出最大值,结束for循环对输出的最短长度进行优化。
下面是AC代码:
#include <cstdio> #include <cstring> #include <cmath> #include <iostream> #include <algorithm> #include <vector> #include <stack> #include <sstream> #include <map> #include <set> #include <queue> #include <stdlib.h> using namespace std; struct sss{ long long x,h; bool operator <(const sss & y) const { if(x!=y.x) return x>y.x; else return h>y.h; } }p; int main() { long long n,k,x; cin >> n >> k; priority_queue<sss>q; for (int i=1;i<=n;i++) { cin >> x; q.push({x,0}); } while((n-1)%(k-1)!=0) { n++; q.push({0,0}); } long long ans1=0; long long ans2=0; while(q.size()>1) { long long xx=0; long long hh=0; for (int i=1;i<=k;i++) { p=q.top(); cout << p.h << " " << p.x << endl; q.pop(); hh=max(p.h,hh); xx+=p.x; } ans1+=xx; ans2=max(ans2,hh+1); q.push({xx,hh+1}); } cout << ans1 << endl << ans2 << endl; return 0; }