o
/ \
o o
/\ /\
o o o o
/\ c d e
o o b
a b
c
叶子节点-初始的各个堆
中间、根节点-合并后的个数
可以发现 和就是 Σ各个叶子节点的值*叶子节点到根节点的距离
$$
sum = \sum_{i}^{n} node[i]*d[i]
$$
$交换b,c前:sum = 3a+3b+2c+2d+2e$
$交换b,c后:sum = 3a+3c+2b+2d+2e$
基于贪心可知:
越大的值放更浅的地方
越小的值放更深的地方
<=>
最小的两个点深度一定最深,且可以互为兄弟
<=>
每次都贪心的合并当前最小的两个点(用堆O(logn)维护)
哈夫曼树是一个有最优子结构的问题
最优子结构-有全局最优解
$n$个点的树做完后还剩$n-1$个点的树,而$n-1$的最优解一定是$n$的最优解
o
/ \
o o
/\ /\
o o o o
/\ c d e
o o
a b
$5$个点合并最小两个点变为$4$个点后
$$
n个点最佳方案 F(n){~}n-1个点最佳方案F(n-1)\\\\
代价 f(n)=f(n-1)+a+b\\\\
目标:求min(f(n))=min(f(n-1))+a+b
$$
o
/ \
o o
/\ /\
o o o o
#include<iostream>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;
int main()
{
int n;
cin >> n;
priority_queue<int,vector<int>,greater<int>> h;
while(n--)
{
int x;
cin >> x;
h.push(x);
}
int res = 0;
while(h.size()>1)
{
int t1 = h.top();h.pop();
int t2 = h.top();h.pop();
res +=t1+t2;
h.push(t1+t2);
}
cout << res << endl;
return 0;
}