/*

哈弗曼編碼，比如權值為 a:1 b:1 c:2 d:3 e:5 f:6 的樹

?? 1.開始時由最小的兩個數 a:1 b:1組成一棵樹

?? 2.接著由新的最小的兩個數 2 c:2 d:3 e:5 f:6 中的 2 c:2組成新的樹

?? 3.接著由最小的兩個數 4 d:3 組成新的樹

?? 4.接著由最小的兩個數 e:5 f:6 組成一棵樹

?? 5.接著由最小的兩個數 7 11 組成一棵樹（最終形成）

?? 6.算最小的編碼總長：= 18 + 7 + 11 + 4 + 2 = 42

?

?? 2??????? 4????????? ?7??????? 11????????? 18

? ?/ \??? ?? / \??? ?? / \??? ?? /? \????? ?? /? \

? a?? b????2?? c?? ? 4?? d???e??? f???? ? 7?? 11

??????? ? ?/ \??????? ?/ \???????????????????/ \? / \

?????? ?? a?? b???? ?2? c?????????????????4? d? e? f

??????????????? ?? ?/ \??????????????? ?? ?/ \

??????????????? ? ?a?? b?????????????? ? 2?? c

???????????????????????????????????? ?? ?/ \

???????????????????????????????????? ?? a?? b

?

可以用優先隊列做，優先隊列每次插入都是插入到排完序后的隊列數組中(可能不是很準確)，

當還沒開始建樹時，把出現的次數進隊，當開始建樹時，每次調用頭兩個數據a和b，然后把兩個數據

相加后，再次進隊，同時優先隊列會進行排序，并且每次ans += a+b,最終答案即為ans

*/

?

#include <iostream>

#include <string>

#include <queue>

#include <vector>

using namespace std;

string s;

int main()

{

?? freopen("sum.in","r",stdin);

?? freopen("sum.out","w",stdout);

?? int n,command;

?? while(cin>>n)

?? {

????? priority_queue<int ,vector<int>,greater<int> > q; //注意，此處> >是有空格的

????? int worst = 0,ans = 0;

????? for(int i=0;i<n;i++)

????? {

???????? cin>>s>>command;

???????? worst+=command*s.size();??? //最壞情況需要的空間

???????? q.push(command);??????????? //把數據進隊

????? }

????? int a,b;

????? if(q.size()==1)??????????????? //當之有一個串時

???????? ans = q.top();

????? while(true)

????? {

???????? a = q.top();

???????? q.pop();

???????? if(q.empty())?? //只剩下一個根節點，就已經構成了一棵樹

??????????? break;

???????? b = q.top();

???????? q.pop();

???????? ans+=a+b;?? //答案

???????? q.push(a+b); //把新生成的樹的權值進隊

????? }

????? cout<<worst<<" "<<ans<<endl;

?? }

?? return 0;

}

?

poj3253Fence Repair

#include <iostream>

#include <queue>

#include <vector>

using namespace std;

int main()

{

?? freopen("sum.in","r",stdin);

?? freopen("sum.out","w",stdout);

?? int n,t,a,b;

?? while(cin>>n)

?? {

????? long long ans = 0;??? //要為long long型才不會WA

????? priority_queue<int ,vector<int>,greater<int> > q;

????? for(int i=0;i<n;i++)

????? {

???????? cin>>t;

???????? q.push(t);

????? }

????? if(q.size()==1)

???????? ans = q.top();

????? while(q.size()>1)

????? {

???????? a = q.top();

???????? q.pop();

???????? b = q.top();

???????? q.pop();

???????? ans += a+b;

???????? q.push(a+b);

????? }

????? cout<<ans<<endl;

?? }

?? return 0;

}

?

?

轉載于:https://www.cnblogs.com/yejinru/archive/2012/03/21/2410367.html

總結

以上是生活随笔為你收集整理的hoj2677 Instruction Set // poj3253Fence Repair 哈夫曼树的全部內容，希望文章能夠幫你解決所遇到的問題。

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