Luogu

分析

显然我们要求的是一个高度最小的 $k$ 叉 Huffman 树。

那么每次找 $k$ 个权值最小的点合并成一个即可，如果权值相同则优先选合并次数小的。

注意最后可能会剩下 $<k$ 个节点，所以一开始要补一些空节点使得最后正好留下一个。

代码

// ===================================
//   author: M_sea
//   website: http://m-sea-blog.com/
// ===================================
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <vector>
#include <cmath>
#include <queue>
#define re register
#define int long long
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

int n,k;

typedef pair<int,int> pii;
priority_queue<pii,vector<pii>,greater<pii> > Q;

signed main() {
    n=read(),k=read();
    for (re int i=1;i<=n;++i) Q.push(make_pair(read(),0));
    while ((Q.size()-1)%(k-1)) Q.push(make_pair(0,0));
    int ans=0;
    while (Q.size()>=k) {
        pair<int,int> now=make_pair(0,0);
        for (re int i=1;i<=k;++i) {
            now.first+=Q.top().first;
            now.second=max(now.second,Q.top().second+1);
            Q.pop();
        }
        ans+=now.first,Q.push(now);
    }
    printf("%lld\n%lld\n",ans,Q.top().second);
    return 0;
}