哈夫曼樹 哈夫曼樹（Huffman tree），又名最優(yōu)樹，指給定n個(gè)權(quán)值作為n的葉子結(jié)點(diǎn)，構(gòu)造一棵二叉樹，若帶權(quán)路徑長度達(dá)到最小，稱這樣的二叉樹為最優(yōu)二叉樹，也稱為哈夫曼樹(Huffman tree)。哈夫曼樹是帶權(quán)路徑長度最短的樹，權(quán)值較大的結(jié)點(diǎn)離根較近。若將樹中結(jié)點(diǎn)賦給一個(gè)有著某種含義的數(shù)值，則這個(gè)數(shù)值稱為該結(jié)點(diǎn)的權(quán)。
#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); } 按順序是找到兩段長度最相近的切下去，然后依次進(jìn)行； 所以我們可以按照逆序，找到兩段最短的求和，扔進(jìn)set，再重復(fù)操作，直到set里只有一根最長的。新聞熱點(diǎn)
疑難解答
圖片精選
網(wǎng)友關(guān)注
