传送门

文章目录

• 题目描述
• 解析
• • 细节
• 代码

题目描述

解析

其实就是构造一棵树
另所有带权点都为叶子节点
其代价为权值与深度的乘积
求最小代价及最小代价下的最小深度

可以看成一开始有n棵小树
每次把k棵合并在一起
最后合成一棵大树就行了
每次合并的代价是k棵树的权值和
看到这个我们不禁想到了合并果子
自然想到用堆来维护最小值
注意由于要保证深度最小所以要双关键字排序
权值相同时按树的深度排序

细节

1.当(q.size()-1)%(k-1)！=0时，需要填一些空点使其能被恰好填满
2.注意最后深度要减1

代码

#include <bits/stdc++.h> using namespace std; #define ll long long const int N=4e6+2e5+100; const int M=3e5+100; ll n,m,k; ll w[N]; struct node{ll num,len;bool operator < (const node y)const{if(num==y.num) return len>y.len;return num>y.num;} }; priority_queue<node>q; ll tot,mx=1; int main(){scanf("%lld%lld",&n,&k);for(int i=1;i<=n;i++){scanf("%lld",&w[i]);q.push((node){w[i],1});//tot+w[i];}while((q.size()-1)%(k-1)) q.push((node){0,1});while(q.size()!=1){ll ww=0,h=0;for(int i=1;i<=k;i++){node x=q.top();q.pop();ww+=x.num;h=max(h,x.len);}tot+=ww;q.push((node){ww,h+1});mx=max(mx,h+1);}printf("%lld\n%lld",tot,mx-1);return 0; } /* 10 7 7 2 2 1 2 4 2 1 7 2 2 7 3 4 2 2 4 4 1 6 7 3 7 7 1 7 5 2 5 2 1 */

总结

以上是生活随笔为你收集整理的P2168 [NOI2015] 荷马史诗（哈夫曼编码树）的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。