关于Huffman树：
大概就是那样子吧。
是这样的：对于最多只能有k个叉的树，我们想要使得∑val(i) * deep(i)最大
那么我们补0后建立小根堆即可。
最典型例题：合并果子。
然后是这个：
/**************************************************************
Problem: 4198
Language: C++
Result: Accepted
Time:1032 ms
Memory:3896 kb
****************************************************************/ #include <cstdio>
#include <queue>
const int N = ;
typedef long long LL;
inline void max(LL &a, LL b) {
if(a < b) a = b;
return;
}
struct Node {
LL val, p;
bool operator < (const Node &x) const {
if(val != x.val) {
return val > x.val;
}
return p > x.p;
}
}; std::priority_queue<Node> Q; Node mk(LL v, LL p) {
Node ans;
ans.val = v;
ans.p = p;
return ans;
} int main() {
LL n, k, v;
scanf("%lld%lld", &n, &k);
for(int i = ; i <= n; i++) {
scanf("%lld", &v);
Q.push(mk(v, ));
}
while((n - ) % (k - ) != ) {
Q.push(mk(, ));
n++;
} LL ans = ; for(int i = ; i <= (n - ); i += (k - )) {
LL p = ;
v = ;
for(int j = ; j <= k; j++) {
Node nd = Q.top();
Q.pop();
max(p, nd.p);
v += nd.val;
}
ans += v;
Q.push(mk(v, p + ));
}
LL p = Q.top().p;
printf("%lld %lld", ans, p);
return ;
}
AC代码
之前写的太菜了......
对于这种要让叶权值 * 深度最小的最多k叉树，通解就是每层放k - 1个，然后多的一个向下延伸。
从下往上着构造，要添加0补全。
然后，可以用蚯蚓的套路优化常数(有排序的复杂度)。
如果给定的是有序的或者能够桶排，就能做到O(n + k)。
#include <cstdio>
#include <algorithm>
#include <queue> typedef long long LL;
const int N = ; struct Node {
LL val, deep;
inline bool operator <(const Node &w) const {
if(val == w.val) {
return deep < w.deep;
}
return val < w.val;
}
Node(LL a = , LL b = ) {
val = a;
deep = b;
}
}a[N]; int top, head = ; std::queue<Node> Q; inline Node getmin() {
if(Q.empty()) {
return a[head++];
}
if(head > top || Q.front() < a[head]) {
Node t = Q.front();
Q.pop();
return t;
}
return a[head++];
} int main() {
LL n, k;
scanf("%lld%lld", &n, &k);
for(int i = ; i <= n; i++) {
scanf("%lld", &a[i].val);
a[i].deep = ;
} while((n - ) % (k - )) {
n++;
a[n].deep = ;
}
std::sort(a + , a + n + );
LL ans = , d = , lm = (n - ) / (k - );
top = n;
for(int i = ; i <= lm; i++) {
Node s;
for(int j = ; j <= k; j++) {
Node t = getmin();
s.val += t.val;
s.deep = std::max(s.deep, t.deep);
}
s.deep++;
Q.push(s);
ans += s.val;
d = std::max(d, s.deep);
} printf("%lld\n%lld\n", ans, d - );
return ;
}
新版AC代码