資料結構與算法——7-29 修理牧場 (25分)

7-29 修理牧場 (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（≤104），表示要将木頭鋸成N塊。第二行給出N個正整數（≤50），表示每段木塊的長度。

輸出格式:

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

思路：考察哈夫曼樹，即最優二叉樹 帶權路徑長度最小的樹，

從小到大排序，每次選取結點權值最小的合并再插入在合适的位置上，如此循環往複，直到vector中隻有一個元素時停止

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
    vector <int> v;
    int n,i,x;
    cin>>n;
    for(i = 0; i < n; i++) {
    	cin>>x;
    	v.push_back(x);
	}
	sort(v.begin(), v.end());
	int sum = 0,ans=0;
	while(v.size() > 1) {
		sum = v[0] + v[1];
		ans += sum;
		v.erase(v.begin());
		v.erase(v.begin());
		if(!v.empty()) {
			int flag = 0;
			for(i = 0; i < v.size(); i++) {
				if(v[i] >= sum) { 
					v.insert(v.begin() + i, sum);
					flag = 1;
					break;
				}
			}
			if(flag == 0) v.push_back(sum);//如果sum比v裡面的都大 就放在最後
		}
	}
    cout<<ans;
	
    return 0;
}