感谢所有AC

传送门

思路

       k进制的哈夫曼树模板。

       每个结点内存储权值和高度，以权值为第一关键词，高度为第二关键词建立一个优先队列。每一次操作都把权值最小的 k 个数取出，合并后加入堆中（哈夫曼算法）。在最后一次合并时可能出现堆中元素不足 k 个，如果直接合并的话会出现哈夫曼树上还有短编码的空位却没有进行填充（即得不到最优解，离树根近的位置没有得到利用）。所以在堆内加入权值为 0 的结点来保证所有位置的合理利用，且这样并不会影响哈夫曼算法的准确性。在建树过程中计算WPL并求解最大深度。

代码

#include
#include
#include
using namespace std;
struct node{
	long long w, l;
};
long long n, k, in, ans;
bool operator<(node a, node b) {
	if (a.w != b.w)return a.w > b.w;
	else return a.l > b.l;
}
//优先队列的结构体定义有点不同，需要注意
priority_queue q;
int main(void)
{
	ios::sync_with_stdio(false);
	cin >> n >> k;
	for (int i = 1; i <= n; i++)
	{
		cin >> in;
		q.push({ in,1 });
	}
	long long add = (n - 1) % (k - 1);
	if (add) {
		for (int i = 1; i <= k - 1 - add; i++)
			q.push({ 0,1 });
        //差多少补多少
	}
	while (q.size() != 1) {
		long long sum = 0, h = 0;
		for (int i = 1; i <= k; i++)
		{
			sum += q.top().w;
			h = max(h, q.top().l);//取最大深度
			q.pop();
		}
		ans += sum;
        //在构造哈夫曼树过程中计算WPL的核心代码
		q.push({ sum,h + 1 });
	}
	cout << ans << '\n' << q.top().l - 1 << '\n';
	return 0;
}