本题主要利用赫夫曼树的原理，
| Time Limit: 2000MS | Memory Limit: 65536K | |
| Total Submissions: 19794 | Accepted: 6276 |
Description
Farmer John wants to repair a small length of the fence around the pasture. He measures the fence and finds that he needsN (1 ≤ N ≤ 20,000) planks of wood, each having some integer lengthLi (1 ≤ Li ≤ 50,000) units. He then purchases a single long board just long enough to saw into theN planks (i.e., whose length is the sum of the lengths Li). FJ is ignoring the "kerf", the extra length lost to sawdust when a sawcut is made; you should ignore it, too.
FJ sadly realizes that he doesn't own a saw with which to cut the wood, so he mosies over to Farmer Don's Farm with this long board and politely asks if he may borrow a saw.
Farmer Don, a closet capitalist, doesn't lend FJ a saw but instead offers to charge Farmer John for each of theN-1 cuts in the plank. The charge to cut a piece of wood is exactly equal to its length. Cutting a plank of length 21 costs 21 cents.
Farmer Don then lets Farmer John decide the order and locations to cut the plank. Help Farmer John determine the minimum amount of money he can spend to create theN planks. FJ knows that he can cut the board in various different orders which will result in different charges since the resulting intermediate planks are of different lengths.
Input
Lines 2..N+1: Each line contains a single integer describing the length of a needed plank
Output
Sample Input
3 8 5 8
Sample Output
34
Hint
The original board measures 8+5+8=21. The first cut will cost 21, and should be used to cut the board into pieces measuring 13 and 8. The second cut will cost 13, and should be used to cut the 13 into 8 and 5. This would cost 21+13=34. If the 21 was cut into 16 and 5 instead, the second cut would cost 16 for a total of 37 (which is more than 34).
解题思路 ：要将长度为n的一个长木板 分成若干短的，分解长度为n的木板需要花费n；
如题中给出要求的3个木板长度，所以最初开始木板长度为 8+5+8=21
将长度为21的木板分解成3段，并且要求花费最少，
第一次分解 21， 分成8和13，
第二次分解 13，分成8和5，此种分法花费最少，但这种分法是什么规则呢？？？？
倒过来逆向思维，将若干个长度的木板拼接成一个，每两个（长度a，b）拼成一个长度为（a+b），就花费 （a+b）元
要使总花费最少，则每次选择长度最小的两个拼接，，就像建立赫夫曼树那样来做
第一次代码：超时，，，，建立一个一位数组，从0开始存元素，dao下标n-1，，，
将它们从大到小排序，，取出后两个相加，将和sum放到数组后面，代替那两个组小值，数组元素--；
然后将数组再次里面排序，取最小值两个，重复，值到剩一个，
每次取出的两个最小的和 累加起来 即为最少花费！！
超时代码：
#include <string.h>
#include <stdio.h>
#include <iostream>
#include <stdlib.h>
#include <algorithm>
using namespace std;
int a[20002];
bool cmp(int a,int b)
{
if(a>b) return true;
return false;
}
void Haffman(int num)
{
/*
4
3 6 1 4
*/
int n = num;
int i;
int sum =0;
while(n--)
{
// printf("sum=%d\n",sum);
sort(a,a+n+1,cmp);
// for(i=0;i<n+1;i++) printf("%d ",a[i]);
// printf("\n");
a[n-1] = a[n]+a[n-1];
sum += a[n-1];
if(n==1) break;
}
printf("%d\n",sum);
}
int main()
{
int i,n;
// int a[10001];
scanf("%d",&n);
for(i=0;i<n;i++)
scanf("%d",&a[i]);
// scanf("%d",&tree[i].weigth);
Haffman(n);
system("pause");
return 0;
}
第二次代码：时间：500MS
其实不用每次都进行排序，第一次排完序之后，将新得到的和直接再插入到数组内即可，数组仍然有序
#include <string.h>
#include <stdio.h>
#include <iostream>
#include <stdlib.h>
#include <algorithm>
using namespace std;
int a[20002];
int cmp(const void * a,const void * b)
{
return *(int *)b - *(int *)a;
}
void Haffman(int num)
{
/*
6
3 6 1 4 5 2
*/
int n = num;
int i,j,k;
long long sum =0;
qsort(a,n,sizeof(int),cmp);
for(i=0;i<n-1;i++)
{
int temp = a[num-1]+a[num-2];
for(j=n-1;j>=0;j--)//将和插入到数组里面
{
if(temp<a[j]) break;
else a[j+1] = a[j];
}
a[j+1] = temp;
sum += temp;//每次的和累加
num--;
}
printf("%lld\n",sum);
}
int main()
{
int i,n;
while(scanf("%d",&n)!=EOF)
{
for(i=0;i<n;i++)
scanf("%d",&a[i]);
if(n==1) printf("0\n");
else Haffman(n);
}
//system("pause");
return 0;
}
下面是别人用的堆排序做的，时间90MS
#include <iostream>
using namespace std;
typedef long long int64;
int len;
int64 arr[20001]; //arr[0] 存数当前数组的长度
//调整堆
void heap(int i) {
int left = i * 2;
int right = i * 2 + 1;
int mins = i;
if (left <= arr[0] && arr[left] < arr[mins])
mins = left;
if (right <= arr[0] && arr[right] < arr[mins])
mins = right;
if (i != mins) {
swap(arr[i], arr[mins]);
heap(mins);
}
}
//想堆中插入一个数
void inheap(int64 key) {
arr[++arr[0]] = key;
int64 i = arr[0];
//i就是当前插入的最后位置. 循环 lgn 次即可
while (i > 1 && arr[i] < arr[i / 2]) {
swap(arr[i], arr[i / 2]);
i = i / 2;
}
}
//返回最小的两个数的和
int64 get() {
int64 p = arr[1], q;
arr[1] = arr[arr[0]]; //第一个位置 和 最后一个位置交换
arr[0]--; //数组长度减1
heap(1); //调整位置1
q = arr[1];
arr[1] = arr[arr[0]];
arr[0]--;
heap(1);
inheap(p + q); //返回最小的两个数的和
return p + q;
}
int main() {
while (cin >> len) {
arr[0] = 0;
for (int i = 1; i <= len; i++) {
cin >> arr[i];
inheap(arr[i]);
}
int64 ans = 0;
for (int i = 1; i < len; i++) {
ans += get();
}
cout << ans << endl;
}
return 0;
}