【BZOJ 4198】[NOI2015] 荷马史诗

相关链接

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=4198

解题报告

k叉哈夫曼树
注意最大化儿子不满的那个结点的深度

Code

#include<bits/stdc++.h>
#define LL long long
using namespace std;

struct Data{
	LL apt, mx;
	inline Data() {
	}
	inline Data(LL a, LL c):apt(a), mx(c) {
	}
	inline Data operator + (const Data &d) {
		return Data(apt + d.apt, max(mx, d.mx + 1));
	}
	inline bool operator < (const Data &d) const {
		return apt > d.apt || (apt == d.apt && mx > d.mx); 
	}
};
priority_queue<Data> que;

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

int main() {
	int n = read(), k = read();
	for (int i = 1; i <= n; i++) {
		que.push(Data(read(), 0));
	} 
	LL ans = 0;
	for (bool frt = (n - 1) % (k - 1); (int)que.size() > 1; frt = 0) {
		Data np(0, 0);
		for (int i = frt? 1 + (n - 1) % (k - 1): k; i; --i) {
			np = np + que.top();
			que.pop();
		}
		ans += np.apt;
		que.push(np);
	}
	printf("%lld\n%lld\n", ans, que.top().mx);
	return 0;
}