哈夫曼树 哈夫曼树（Huffman tree），又名最优树，指给定n个权值作为n的叶子结点，构造一棵二叉树，若带权路径长度达到最小，称这样的二叉树为最优二叉树，也称为哈夫曼树(Huffman tree)。哈夫曼树是带权路径长度最短的树，权值较大的结点离根较近。若将树中结点赋给一个有着某种含义的数值，则这个数值称为该结点的权。
#include <bits/stdc++.h>using namespace std;#define maxn 50010#define LL long longLL arr[maxn];multiset <LL> s;multiset <LL>::iterator it;int main(){// freopen("1.txt","w",stdout); LL n,sum=0,num=0; scanf("%lld", &n); for(int i=1;i<=n;i++) { scanf("%lld", &arr[i]); s.insert(arr[i]); } while(s.size()>1) { LL a=0; it=s.begin(); a+=*it; s.erase(it); it=s.begin(); a+=*it; s.erase(it); sum+=a; s.insert(a); } PRintf("%lld/n", sum);}//哈夫曼树按顺序是找到两段长度最相近的切下去，然后依次进行； 所以我们可以按照逆序，找到两段最短的求和，扔进set，再重复操作，直到set里只有一根最长的。
新闻热点
疑难解答
