3 条题解
-
1
闲言
这不是[模板]哈夫曼树吗,放在这是什么意思?
我写个堆不就完了?
不对,样例二挂了。
是什么??
原来是 叉的哈夫曼树。
前文
以防你不知道什么是哈夫曼树 哈夫曼编码,先来介绍一下。
哈夫曼编码是一种压缩信息量的方法,著名的摩尔斯电码就是采用的这样的编码。
哈夫曼编码的最大特点是编码的长度不等,如摩尔斯电码里的 是一短(要么就是一长,反正他是最短的)。
为什么要这么编码呢?
可以发现 是英语里面最常出现的字母,把他编的短一点应该可以很大降低电报长度,毕竟电报是按字数收钱的。
又比如 等,打几百个字母也就出现几次,编的长一点在整体上更优。
但是我们遇到了一个问题:如何确保信息的准确传递呢?也就是说,怎么才能避免把长编码的一部分错认为短编码呢?
要想保证正确性,必须保证每个编码不是某个编码的前缀。
我们回到 的方向,把每个串插入字典树,可以发现,每个叶子节点到根构成的字符串对应且仅对应一个编码,而非叶子节点不代表任何编码。
我们设编码 的出现概率为 ,长度为 ,则我们希望,编码的期望长度 最小。
由期望的线性性,可以知道 。
贪心地想, 越小的编码长度应该越大,于是我们可以得出 哈夫曼编码的经典构造方法:初始时每个编码对应一个叶子节点,每次取概率最小的两个叶子,将其合并得到一个新叶子,新叶子的概率就是原概率之和。
此处读者感性理解即可,证明详见
OI-wiki。好像一般翻译为霍夫曼树,但是我习惯叫哈夫曼,可能因为我当时这么学的吧。总之到网上搜要搜霍夫曼树。
于是我们得到了经典的二进制哈夫曼算法,这样构造出来的树就是哈夫曼树。
正文
没错,写了这么多,我们终于要开始看这个题了。
我们沿用二进制的算法来做,每次拿出最小的 个点来合并,你会发现这样假了。
原因很简单:如果最后一次合并没有凑齐 个点,我们完全可以从最深的一层拿一个点上来安到根上,这样一定是更优的。
简单归纳一下,可得: 进制哈夫曼算法最开始合并的一个点有小于等于 个儿子,而其他所有非叶子节点都恰好有 个儿子。
于是我们把每种单词扔进堆里,按次数为第一关键字升序,高度为第二关键字升序,特判第一次合并,其他正常做就完事了。
因为要保证长度和最小,所以这样一定能得到正确答案。
细节上,第一次特判要选总点数取模 的结果个点来合并,当 时进入死循环,要特判一下。
代码
非常好写。
#include<bits/stdc++.h> using namespace std; #define int long long #define fi first #define se second int T,n,k; priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > > pq; signed main(){ ios::sync_with_stdio(0); cin.tie(0),cout.tie(0); cin>>n>>k; for(int i=1;i<=n;i++){ int x; cin>>x; pq.push({x,0}); } int ans=0; if(k==2){ while(pq.size()>1){ int s=pq.top().fi,d=pq.top().se; pq.pop(); s+=pq.top().fi,d=max(d,pq.top().se); pq.pop(); ans+=s; pq.push({s,d+1}); } cout<<ans<<'\n'<<pq.top().se<<'\n'; return 0; } while(pq.size()>1){ int c; if(pq.size()%(k-1)==1) c=k; else c=pq.size()%(k-1); if(c==0) c=k-1; int s=0,d=0; while(c--){ s+=pq.top().fi,d=max(d,pq.top().se+1),pq.pop(); } ans+=s; pq.push({s,d}); } cout<<ans<<'\n'<<pq.top().se<<'\n'; return 0; }
信息
- ID
- 939
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 9
- 标签
- (无)
- 递交数
- 123
- 已通过
- 11
- 上传者