傳送門

文章目錄

• 題目描述
• 解析
• • 細節
• 代碼

題目描述

解析

其實就是構造一棵樹
另所有帶權點都為葉子節點
其代價為權值與深度的乘積
求最小代價及最小代價下的最小深度

可以看成一開始有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] 荷马史诗（哈夫曼编码树）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。