又是啃课件的一天
定义
构造一棵含(n)个叶子结点的(k)叉树, 其中第(i)个叶子结点权值(w_i), 要求最小化
(sum w_i*d_i), (d_i)表示(i)结点的深度。
这样的合法的树被称为(k叉)(Huffman)树
构造方法
增加一些叶子结点为(0)的结点, 使得它成为满(k)叉树。将(w)都丢进小根堆，每次都
取前(k)小的(w),和为(s),建立权值为(s)的节点(p),令(p)成为这(k)个结点的父亲, 然后把(s)丢入堆。
证明大概就是要保证权值最小在下面，但是如果不是满(k)叉树会错，于是就补几个(0)(qwq)
感性理解下
应用
这个可以压缩文件的，不过打不过专业软件就对了。
Problem1 NOIP2004 合并果子
想不到吧，二叉Huffman树就可以了,二叉并不用补0。
/*
@Date : 2019-09-06 21:56:05
@Author : Adscn (adscn@qq.com)
@Link : https://www.cnblogs.com/LLCSBlog
*/
#include<bits/stdc++.h>
#include<bits/extc++.h>
using namespace std;
#define IL inline
#define RG register
#define gi getint()
#define gc getchar()
#define File(a) freopen(a".in","r",stdin);freopen(a".out","w",stdout)
template<typename T>IL bool chkmax(T &x,const T &y){return x<y?x=y,1:0;}
template<typename T>IL bool chkmin(T &x,const T &y){return x>y?x=y,1:0;}
IL int getint()
{
RG int xi=0;
RG char ch=gc;
bool f=0;
while(!isdigit(ch))ch=='-'?f=1:f,ch=gc;
while(isdigit(ch))xi=xi*10+ch-48,ch=gc;
return f?-xi:xi;
}
template<typename T>
IL void pi(T k,char ch=0)
{
if(k<0)k=-k,putchar('-');
if(k>=10)pi(k/10,0);
putchar(k%10+'0');
if(ch)putchar(ch);
}
__gnu_pbds::priority_queue<int,greater<int> >p;
int main(void)
{
int n=gi;
for(int i=1;i<=n;++i)p.push(gi);
int ans=0;
while(p.size()>=2){
int w1=p.top();p.pop();
int w2=p.top();p.pop();
int s=w1+w2;
ans+=s;
p.push(s);
}
pi(ans);
return 0;
}
Problem2 NOI2015荷马史诗
k叉Huffman树，维护一下深度就可以了。
所以这玩意除了裸题有什么别的用？
/*
@Date : 2019-09-06 22:03:12
@Author : Adscn (adscn@qq.com)
@Link : https://www.cnblogs.com/LLCSBlog
*/
#include<bits/stdc++.h>
#include<bits/extc++.h>
using namespace std;
#define IL inline
#define RG register
#define gi getint()
#define gc getchar()
#define File(a) freopen(a".in","r",stdin);freopen(a".out","w",stdout)
template<typename T>IL bool chkmax(T &x,const T &y){return x<y?x=y,1:0;}
template<typename T>IL bool chkmin(T &x,const T &y){return x>y?x=y,1:0;}
typedef long long ll;
IL ll getint()
{
RG ll xi=0;
RG char ch=gc;
bool f=0;
while(!isdigit(ch))ch=='-'?f=1:f,ch=gc;
while(isdigit(ch))xi=xi*10+ch-48,ch=gc;
return f?-xi:xi;
}
template<typename T>
IL void pi(T k,char ch=0)
{
if(k<0)k=-k,putchar('-');
if(k>=10)pi(k/10,0);
putchar(k%10+'0');
if(ch)putchar(ch);
}
typedef pair<ll,int> pll;
__gnu_pbds::priority_queue<pll,greater<pll> >q;
#define fi first
#define se second
#define mp make_pair
int main(void)
{
int n=gi,k=gi;
for(int i=1;i<=n;++i)q.push(mp(gi,0));
while((n-1)%(k-1))q.push(mp(0,0)),++n;
ll ans=0;
while(n>1){
ll sum=0;
int mh=0;
for(int i=1;i<=k;++i)sum+=q.top().fi,chkmax(mh,q.top().se),q.pop();
ans+=sum;
q.push(mp(sum,mh+1));
n-=k-1;
}
pi(ans,'
'),pi(q.top().se);
return 0;
}