7-1 修理牧場 (25 分)（最詳解）（最容易理解的解題過程）

農夫要修理牧場的一段柵欄，他測量了柵欄，發現需要N塊木頭，每塊木頭長度為整數L?i??個長度單位，于是他購買了一條很長的、能鋸成N塊的木頭，即該木頭的長度是L?i??的總和。

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

請編寫程序幫助農夫計算將木頭鋸成N塊的最少花費。

輸入格式:

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

輸出格式:

輸出一個整數，即將木頭鋸成N塊的最少花費。

輸入樣例:

8 4 5 1 2 1 3 1 1

輸出樣例:

49

題目解釋：利用建造哈夫曼樹的思想? 根據葉節點的權值 排序（升序）（模仿最小堆） 將其所有葉節點的權值入隊? 當然我們入的是C++中的優先隊列（模仿最小堆）

分享C++中 被調用的 優先隊列類及其方法

優先隊列具有隊列的所有特性，包括基本操作，只是在這基礎上添加了內部的一個排序，它本質是一個堆實現的

和隊列基本操作相同:

top 訪問隊頭元素
empty 隊列是否為空
size 返回隊列內元素個數
push 插入元素到隊尾 (并排序)
emplace 原地構造一個元素并插入隊列
pop 彈出隊頭元素
swap 交換內容
定義：priority_queue<Type, Container, Functional>
Type 就是數據類型，Container 就是容器類型（Container必須是用數組實現的容器，比如vector,deque等等，但不能用 list。STL里面默認用的是vector），Functional 就是比較的方式，當需要用自定義的數據類型時才需要傳入這三個參數，使用基本數據類型時，只需要傳入數據類型，默認是大頂堆
一般是：

//升序隊列
priority_queue <int,vector<int>,greater<int> > q;
//降序隊列
priority_queue <int,vector<int>,less<int> >q;

//哈夫曼樹 #include<bits/stdc++.h> using namespace std; int main(){priority_queue <int,vector<int>,greater<int> > q;//優先隊列 中 升序隊列int N,i,j,k,a[10000],d[10000],sum=0;scanf("%d",&N);for(i=0;i<N;i++){scanf("%d",&a[i]);}for(i=0;i<N;i++){q.push(a[i]);}while(!q.empty()&&q.size()!=1){int temp1= q.top();//先訪問 再彈出 q.pop();int temp2= q.top();q.pop();int temp=temp1+temp2;sum+=temp;q.push(temp);} printf("%d",sum); }

總結

以上是生活随笔為你收集整理的7-1 修理牧场 (25 分)（最详解）（最容易理解的解题过程）的全部內容，希望文章能夠幫你解決所遇到的問題。

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