算法|修理牧场算法|c语言

农夫要修理牧场的一段栅栏，他测量了栅栏，发现需要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

??用堆,又效率又简单,堆肯定比排序快,养成代码洁癖从写题开始,这里Max要设置为10001,血的教训,堆用了一个哨兵,改来改去不知道哪错了,兜兜转转看别人的代码,发现都不如自己的,傻看了半小时才发现原来是Max出问题,服了,顺带说一句,直接搬运哈夫曼的模板内存多了十倍,而且比排序快了好多倍,还是自己代码香,相信自己嗷
示例代码:

#include #include #define Max 10001 #define INF -1void BulidHeap(); void Insert(int n); void Calculate(); int Delete(); typedef struct HeapStruct MinHeap; struct HeapStruct{ int Data[Max]; int Size; }; MinHeap H; int Sum; int main() { BulidHeap(); Calculate(); printf("%d",Sum); }void BulidHeap() { int N,i,n; H.Data[0] = INF; //哨兵 scanf("%d",&N); for(i = 1; i <= N; i++){ scanf("%d",&n); Insert(n); } }void Insert(int n) { int i; i = ++H.Size; for( ; H.Data[i / 2] > n; i /= 2){ H.Data[i] = H.Data[i / 2]; } H.Data[i] = n; }void Calculate() { int a1,a2; while(H.Size > 1){ a1 = Delete(); a2 = Delete(); Insert(a1 + a2); Sum = Sum + a1 + a2; } }int Delete() { int parent,child,t,n; n = H.Data[1]; t = H.Data[H.Size--]; for(parent = 1; parent * 2 <= H.Size; parent = child){ child = parent * 2; if(H.Data[child + 1] < H.Data[child]){ child++; } if(t <= H.Data[child]) break; else{ H.Data[parent] = H.Data[child]; } } H.Data[parent] = t; return n; }