相关链接
题目传送门: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; }