一定要亲自动手写，才能发现哈夫曼树代码的一些细节！把这题认真做完后，相信你笔试遇到手搓哈夫曼树的题一定不会再错了。

#include <iostream>
#include <queue>
using namespace std;
typedef long long ll;

struct node {
	ll w, h; // 该单词出现次数，单词编码后所在的树层
	// 注意！！！因为哈夫曼树的构造过程是从底往上的，
	// 为了方便计算深度，要倒过来记，叶节点深度为1。
	// h也可以理解成，本层及以下一共构造出了几层节点。

	// 优先按w升序排列，w相同则优先选下挂子树层数少的节点（h小）。
	bool operator < (const node& a) const {
		// w相同则优先选下挂子树层数少的节点（h小）。
		// 一定要注意这里h的含义！！！
		if (w == a.w) return h > a.h;
		return w > a.w; // 优先按w升序排列
	} // 也可以用pair，但为了说明清楚，这里用struct
	// 重载运算符这里也是一个代码细节！！！为什么升序重载 < 时
	// return的却是 > ？不是应该也 < 吗？注意优先队列是大根堆！
	// 所以当然要反过来了！！！
};

int main() {
	int n, k;
	cin >> n >> k;
	priority_queue<node> q;
	ll w;
	for (int i = 1; i <= n; i++) {
		cin >> w;
		q.push({w, 1}); // 其实node的h你也可以理解成，
		// 这个节点会在计算总的WPL（带权路径长度）时要被算几次。
	}
	// 为了得到最优构造，需要补充若干权值为0的叶结点。这里的计算请参考课件。
	if ((n - 1) % (k - 1)) {
		int sup = k - 1 - (n - 1) % (k - 1);
		for (int i = 1; i <= sup; i++) q.push({0, 1});
	}

	ll ans = 0;
	while (q.size() > 1) {
		ll h = -1, w = 0;
		for (int i = 1; i <= k; i++) {
			node now = q.top();
			q.pop();
//			printf("dbg: %lld, %lld\n", now.w, now.h);
			// 当前合并的节点其下面可能挂有子树，
			// 所以要找出这一批合并节点的最大深度，
			// 然后这一层节点的深度就是max+1
			h = max(h, now.h);
			w += now.w; // 注意！！！把w往上传递的过程中，
			// 其被重复加了多次，最后总数就等于编码长度*w。
			// 不理解的话，对着课件上的树走一遍程序。
		}
		ans += w;
		// 这一层节点的深度就是max+1
		q.push({w, h + 1});
	}

	cout << ans << '\n' << (q.top().h - 1);

	return 0;
}