对于一个k叉（k>2）的哈夫曼树 ，设其k度节点数为n，叶节点数目为m，则有kn条边。自然得到kn = N（总节点数）- 1。
N = m+n -> kn = m + n -1
则n(k-1) = m -1
则（m-1）%(k-1)可以整除，满足要求即可。
#include <iostream>
#include <vector>
#include <cstdio>
#include<cstdlib>
#define maxn 300050
using namespace std;
typedef long long ll;
struct heap{
int size;
ll heap[maxn];
int maxsize;
};
struct heap *h=(struct heap *)malloc(sizeof(struct heap));;
void insertheap(struct heap * h,ll x){
int i;
for(i = ++h->size; h->heap[i/2]>x; i/=2)
h->heap[i] = h->heap[i/2];
h->heap[i] = x;
}
ll deleteheap(struct heap* h){
ll minx = h->heap[1];
ll last = h->heap[h->size--];
int child,i;
for( i=1; i*2 <= h->size; i = child){
child = i*2;
if(child != h->size && h->heap[child+1] < h->heap[child])
child++;
if(last > h->heap[child])
h->heap[i] =h->heap[child];
else
break;
}
h->heap[i] = last;
return minx;
}
int main() {
int n,k;
scanf("%d",&n);
scanf("%d",&k);
ll word[maxn];
for(int i=0; i<n; ++i){
scanf("%lld",&word[i]);
}
h->heap[0] = -1;
h->size = 0;
h->maxsize = maxn;
for(int i=0; i<n; i++)
insertheap(h, word[i]);
if((n-1)%(k-1)){
int r = (k-1) - (n-1)%(k-1);
for(int i=0; i<r; i++)
insertheap(h,0);
}
//cout<<h->size<<endl;
ll sum = 0;
while(h->size > 1){
ll newsum = 0;
for(int i=0; i<k; i++){
newsum = newsum + deleteheap(h);
}
sum+=newsum;
insertheap(h, newsum);
//cout<<h->size<<endl;
}
//sum += deleteheap(h);
cout<<sum<<endl;
return 0;
}
