[UOJ 130]【NOI2015】荷马史诗：哈夫曼树

本文主要是介绍[UOJ 130]【NOI2015】荷马史诗：哈夫曼树，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

点击这里查看原题

二叉哈夫曼树教程：http://blog.csdn.net/shuangde800/article/details/7341289
这里是k叉哈夫曼树，依然采取贪心策略，不过需要注意的是首先要判断(n-1)%(k-1)是否为0，不为0则要添加权值为0的节点直到(n-1)%(k-1)=0
这是因为，每次合并操作会取出k个点，放进1个点，即每次减少k-1个点。而最终目标是使n个点变为1个点，因此需要用(n-1)%(k-1)来判断

/*
User:Small
Language:C++
Problem No.:130
*/
#include<bits/stdc++.h>
#define ll long long
#define inf ((ll)1<<60)
#define pli pair<ll,int>
#define mp make_pair
using namespace std;
int n,k,nn;
ll ans; 
priority_queue<pli,vector<pli>,greater<pli> > q;
int main(){freopen("data.in","r",stdin);//ios::sync_with_stdio(false);cin>>n>>k;nn=n;for(int i=1;i<=n;i++){ll x;cin>>x;q.push(mp(x,0));}if((n-1)%(k-1)) nn+=(k-1)-(n-1)%(k-1);for(int i=n+1;i<=nn;i++) q.push(mp(0,0));while(nn!=1){ll tot=0;int fl=0;for(int j=1;j<=k;j++){pli now=q.top();q.pop();tot+=now.first;fl=max(fl,now.second+1);}ans+=tot;q.push(mp(tot,fl));nn-=k-1;}pli fir=q.top();cout<<ans<<endl<<fir.second<<endl;return 0;
}

这篇关于[UOJ 130]【NOI2015】荷马史诗：哈夫曼树的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---