题目链接

Solution [NOI2015]荷马史诗

题目大意:构造\(k\)叉哈夫曼树

分析:这题比较模板,可以当做复习初赛(大雾)

哈夫曼树的定义:

构造一棵有\(n\)个节点的\(k\)叉树,每个节点带有权\(w_i\),深度\(d_i\)(规定根深度为\(0\)),使得\(\sum w_i \times d_i\)最小

当\(k=2\)时即为合并果子,因此可以想出显而易见的贪心算法,每次从堆中取\(k\)个合并,但是这样可能根节点的儿子不足\(k\)个,此时将叶节点移为根节点儿子会使得答案更优

因此我们需要额外补足一些\(w=0\)的虚拟点,让儿子不足的情况发生在叶子结点

每次将\(k\)个节点合并使得总个数减少\(k-1\)个,使得\(n\)个节点合并为\(1\)个减少了\(n-1\)个,因此当\((k-1) | (n-1)\)时上述贪心算法正确

题目还要求代价和最小时最大深度尽量小,权值相同时按照深度排序即可

#include <cstdio>
#include <cctype>
#include <queue>
using namespace std;
typedef long long ll;
inline ll read(){
    ll x = 0;char c = getchar();
    while(!isdigit(c))c = getchar();
    while(isdigit(c))x = x * 10 + c - '0',c = getchar();
    return x;
}
struct HeapNode{
    ll val;
    int dep;
    bool operator < (const HeapNode &rhs)const{
        return (val == rhs.val) ? (dep > rhs.dep) : val > rhs.val;
    }
};
priority_queue<HeapNode> Q;
int n,k;
ll ans1,ans2;
int main(){
    n = read(),k = read();
    for(int i = 1;i <= n;i++)
        Q.push(HeapNode{read(),0});
    while((n - 1) % (k - 1))Q.push(HeapNode{0,0}),n++;
    while(Q.size() != 1){
        ll add1 = 0,add2 = 0;
        for(int i = 1;i <= k;i++){
            HeapNode h = Q.top();Q.pop();
            add1 += h.val;
            add2 = max(add2,(ll)h.dep);
        }
        ans1 += add1;
        ans2 = max(ans2,add2 + 1);
        Q.push(HeapNode{add1,add2 + 1});
    }
    printf("%lld\n%lld\n",ans1,ans2);
    return 0;
}