n個節(jié)點k叉。（如果（n-1）%（k-1）！=0）先合并（n-1）%（k-1）+1個節(jié)點再k個K個合并

#include<bits/stdc++.h>
using namespace std;
long long a[1005];
queue<long long> q1,q2;
long long hafuman(int n,int k)
{while(!q2.empty()) q2.pop();int temp;long long sum=0,t;if((n-1)%(k-1)==0)temp=k;else temp=(n-1)%(k-1)+1;while(temp--){sum+=q1.front();q1.pop();}t=sum;q2.push(sum);temp=k;while(!q1.empty()){sum=0;for(int i=0;i<k;i++){if(!q2.empty()&&!q1.empty()){if(q1.front()>q2.front()){sum+=q2.front();q2.pop();}else{sum+=q1.front();q1.pop();}}else if(!q1.empty()){sum+=q1.front();q1.pop();}else {sum+=q2.front();q2.pop();}}t+=sum;q2.push(sum);}if(q2.size()==1)return t;else{while(1){sum=0;for(int i=0;i<k;i++){sum+=q2.front();q2.pop();}t+=sum;q2.push(sum);if(q2.size()==1)return t;}}}
int main()
{int n,k;while(~scanf("%d %d",&n,&k)){for(int i=0;i<n;i++)scanf("%lld",&a[i]);sort(a,a+n);for(int i=0;i<n;i++)q1.push(a[i]);long long ans=hafuman(n,k);printf("%lld\n",ans);}}

總結(jié)

以上是生活随笔為你收集整理的xdoj 1144 K叉哈弗曼树的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。