是个多叉huffman树,思想类比合并果子。
具体见 CrazyDave 的博客
CODE
#include
using namespace std;
typedef long long LL;
struct node {
LL w, h;
node(){}
node(LL w, LL h):w(w), h(h){}
inline bool operator return w == o.w ? h > o.h : w > o.w;
}
};
priority_queueq;
int n, k;
int main () {
scanf("%d%d", &n, &k);
LL x, ans = 0;
for(int i = 1; i scanf("%lld", &x);
q.push(node(x, 1));
}
int cnt = ((k-1) - (n-1)%(k-1)) % (k-1);
while(cnt--) q.push(node(0, 1));
cnt = q.size();
while(cnt > 1) {
LL w = 0, h = 0;
for(int i = 1; i w += q.top().w, h = max(h, q.top().h), q.pop();
ans += w;
q.push(node(w, h+1));
cnt -= k-1;
}
printf("%lldn%lldn", ans, q.top().h-1);
}