郑州网络推广技术_口碑营销的定义_免费十大软件大全下载安装_做网站企业

前言

哈夫曼树

代码

#include<bits/stdc++.h>
using namespace std;
int main(){int n;cin>>n;//输入果子的个数priority_queue<int,vector<int>,greater<int>> heap;//小根堆存了三个参数，记住就好for(int i=0;i<n;i++){int x;cin>>x;heap.push(x);//把所有元素存入小根堆}int ans=0;while(heap.size()>1){//只要小根堆里面的元素至少有两个int a=heap.top();//取出最小值heap.pop();int b=heap.top();//取出次小值ans+=a+b;heap.pop();heap.push(a+b);//构造哈夫曼树，哎不知道是不是哈夫曼树，反正就是把最小的}//两个元素更新为一个新的节点，存到小根堆里面cout<<ans<<endl;return 0;
}

思路

每一次都是合并最小的两堆，合并之后是新的一堆，每次选最小的两堆就是贪心策略，我们每一次都试图选最优的那个选择，最后能不能得到最优解呢，最优解是什么呢。小根堆维护的是最小值。这题好简单。