?

農(nóng)夫要修理牧場(chǎng)的一段柵欄，他測(cè)量了柵欄，發(fā)現(xiàn)需要N塊木頭，每塊木頭長(zhǎng)度為整數(shù)L?i??個(gè)長(zhǎng)度單位，于是他購(gòu)買了一條很長(zhǎng)的、能鋸成N塊的木頭，即該木頭的長(zhǎng)度是L?i??的總和。

但是農(nóng)夫自己沒有鋸子，請(qǐng)人鋸木的酬金跟這段木頭的長(zhǎng)度成正比。為簡(jiǎn)單起見，不妨就設(shè)酬金等于所鋸木頭的長(zhǎng)度。例如，要將長(zhǎng)度為20的木頭鋸成長(zhǎng)度為8、7和5的三段，第一次鋸木頭花費(fèi)20，將木頭鋸成12和8；第二次鋸木頭花費(fèi)12，將長(zhǎng)度為12的木頭鋸成7和5，總花費(fèi)為32。如果第一次將木頭鋸成15和5，則第二次鋸木頭花費(fèi)15，總花費(fèi)為35（大于32）。

請(qǐng)編寫程序幫助農(nóng)夫計(jì)算將木頭鋸成N塊的最少花費(fèi)。

輸入格式:

輸入首先給出正整數(shù)N（≤10?4??），表示要將木頭鋸成N塊。第二行給出N個(gè)正整數(shù)（≤50），表示每段木塊的長(zhǎng)度。

輸出格式:

輸出一個(gè)整數(shù)，即將木頭鋸成N塊的最少花費(fèi)。

輸入樣例:

8 4 5 1 2 1 3 1 1

輸出樣例:

49

?題解：在百度百科上了解到了哈夫曼樹的定義：

結(jié)點(diǎn)的帶權(quán)路徑長(zhǎng)度為從該結(jié)點(diǎn)到樹根之間的路徑長(zhǎng)度與結(jié)點(diǎn)上權(quán)的乘積。樹的帶權(quán)路徑長(zhǎng)度為樹中所有葉子結(jié)點(diǎn)的帶權(quán)路徑長(zhǎng)度之和，通常記作WPL。

若有n個(gè)權(quán)值為w1,w2,...,wn的結(jié)點(diǎn)構(gòu)成一棵有n個(gè)葉子結(jié)點(diǎn)的二叉樹，則樹的帶權(quán)路徑最小的二叉樹叫做哈夫曼樹或最優(yōu)二叉樹。

而這題的模型剛好是哈夫曼樹，然后我們可以利用優(yōu)先隊(duì)列來做這道題：

代碼：

#include<cstdio> #include<cstring> #include<cstring> #include<iostream> #include<queue>using namespace std;int main() {int n;priority_queue<int ,vector<int>,greater<int> >q;cin>>n;int m,sum=0;for(int t=0;t<n;t++){scanf("%d",&m);q.push(m);}int x1,x2;while(q.size()>1){x1=q.top();q.pop();x2=q.top();q.pop();sum+=x1+x2;q.push(x1+x2);}cout<<sum<<endl;return 0; }

?

轉(zhuǎn)載于:https://www.cnblogs.com/Staceyacm/p/10782062.html

總結(jié)

以上是生活随笔為你收集整理的修理牧场(哈夫曼树 )的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。