亚洲一区免费看,亚洲视频一区二区在线观看,永久免费毛片在线播放不卡

P3253

哈夫曼樹
用二叉堆維護logn的最小優(yōu)先隊列

#include <iostream>

using namespace std;

const int MAXN=20001;

int n;

long long num[MAXN];

int len=0;

void insert(long long x)

{

len++;

num[len]=x;

int pos=len;

while(pos>1)

{

if (num[pos]<num[pos/2])

{

swap(num[pos],num[pos/2]);

pos/=2;

}

else break;

}

long long remove()

{

long long x=num[1];

swap(num[1],num[len]);

len--;

int pos=1;

int k;

while(pos*2<=len)

{

int l=pos*2,r=pos*2+1;

if (r>len||num[l]<num[r])

{

k=l;

}

else k=r;

if (num[pos]>num[k]) {swap(num[pos],num[k]);pos=k;} else break;

}

return x;

}

int main()

{

cin>>n;

long long x;

for (int i=1;i<=n;i++)

{

cin>>x;

insert(x);

}

long long result=0;

while(len>1)

{

long long x=remove();

long long y=remove();

long long z=x+y;

result+=z;

insert(z);

}

cout<<result<<endl;

system("pause");

return 0;

}

posted on 2009-10-24 12:30 Vincent 閱讀(91) 評論(0) 編輯收藏引用所屬分類: 數據結構與算法

只有注冊用戶登錄后才能發(fā)表評論。
【推薦】100%開源！大型工業(yè)跨平臺軟件C++源碼提供，建模，組態(tài)！

相關文章: P3368 P2352 dinic P3273 P2104 ctsc2000 丘比特的煩惱 usaco 4.3 lgame P3267 P1276 P1837

網站導航: 博客園 IT新聞 BlogJava 博問 Chat2DB 管理

巢穴

My Links

Blog Stats

News

常用鏈接

留言簿(1)

隨筆分類

隨筆檔案

文章檔案

Link

搜索

最新評論

閱讀排行榜

評論排行榜

P3253