数据结构课设 修理牧场 （哈夫曼树基础）
发布时间
阅读量：
阅读量
5-13 修理牧场 (25分)
农夫首先量度了栅栏的长度，并经计算得出总共需要N块木头，每块长度为整数L_i个单位。为了满足需求并精确地满足每个部分的需求, 他决定购买一条足够长且可分割成N段的具体木料
然而农夫自身并无一把锯子,若请他人切割木材,则酬劳按所切割木料的长度计价.为了简便起见,不妨就设酬金等于所切木头的长度.举个例子来说,将一根长度为20的木材切成长度分别为8、7和5的三段,第一次切割花费了20单位,将其分割为12和8两部分;第二次切割耗费了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和poj3253差不多，只不过数据弱了很多，排个序用vector就可以过。
#include <iostream>
#include <cstring>
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
vector <int> v;
int n;
scanf("%d", &n);
int i;
int x;
for(i = 0; i < n; i++) {
scanf("%d", &x);
v.push_back(x);
}
sort(v.begin(), v.end());
vector <int>::iterator it;
int sum = 0;
int 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);
}
}
printf("%d\n", ans);
return 0;
}全部评论 (0)
还没有任何评论哟~