5-12 修理牧场 (25分)——最小堆->哈夫曼树+快速排序

拼搏现实的明天。 2022-09-30 06:54 142阅读 0赞

think:  
1通过最小堆生成哈夫曼树+快速排序

5-12 修理牧场 (25分)

农夫要修理牧场的一段栅栏，他测量了栅栏，发现需要NNN块木头，每块木头长度为整数LiL\_iLi个长度单位，于是他购买了一条很长的、能锯成NNN块的木头，即该木头的长度是LiL\_iLi的总和。  
但是农夫自己没有锯子，请人锯木的酬金跟这段木头的长度成正比。为简单起见，不妨就设酬金等于所锯木头的长度。例如，要将长度为20的木头锯成长度为8、7和5的三段，第一次锯木头花费20，将木头锯成12和8；第二次锯木头花费12，将长度为12的木头锯成7和5，总花费为32。如果第一次将木头锯成15和5，则第二次锯木头花费15，总花费为35（大于32）。  
请编写程序帮助农夫计算将木头锯成NNN块的最少花费。

输入格式:  
输入首先给出正整数NNN（≤104\\le 10^4≤104），表示要将木头锯成NNN块。第二行给出NNN个正整数（≤50\\le 50≤50），表示每段木块的长度。

输出格式:  
输出一个整数，即将木头锯成NNN块的最少花费。

输入样例:  
8  
4 5 1 2 1 3 1 1

输出样例:

Hint:

测试点1    答案正确    12/12   1   1   sample
    测试点2    答案正确    1/1     2   1   只有一段木头，不用锯
    测试点3    答案正确    6/6     5   1   最大N，最长木段，输出的最大值
    测试点4    答案正确    6/6     6   1   最大N随机数据

以下为答案正确代码

#include <stdio.h>
    #include <stdlib.h>
    #define MINDATA -1
    typedef struct node
    {
        int *Data;
        int Size;
    }MinHeap;
    MinHeap * Creat(int MaxSize)
    {
        MinHeap *H = (MinHeap *)malloc(sizeof(MinHeap));
        H->Data = (int *)malloc((MaxSize + 1)*sizeof(int));
        H->Size = 0;
        H->Data[0] = MINDATA;
        return H;
    }
    void Insert(MinHeap *H, int x)
    {
        int i = ++H->Size;
        for(; H->Data[i/2] >= x; i /= 2)
            H->Data[i] = H->Data[i/2];
        H->Data[i] = x;
    }
    int Delete(MinHeap *H)
    {
        int MinItem, X, parent, child;
        MinItem = H->Data[1];
        X = H->Data[H->Size--];
        for(parent = 1; parent*2 <= H->Size; parent = child)
        {
            child = parent*2;
            if((child != H->Size) && H->Data[child] > H->Data[child+1])
                child++;
            if(X <= H->Data[child])
                break;
            else
                H->Data[parent] = H->Data[child];
        }
        H->Data[parent] = X;
        return MinItem;
    }
    void PercDown(MinHeap *H, int p)
    {
        int X, parent, child;
        X = H->Data[p];
        for(parent = p; parent*2 <= H->Size; parent = child)
        {
            child = parent*2;
            if((child != H->Size) && H->Data[child] > H->Data[child+1])
                child++;
            if(X <= H->Data[child])
                break;
        }
        H->Data[parent] = X;
    }
    void GetBuild(MinHeap *H)
    {
        for(int i = H->Size/2; i > 0; i--)
        {
            PercDown(H, i);
        }
    }
    int cmp(const void *a, const void *b)
    {
        return ((*(int *)a) - (*(int *)b));
    }
    int main()
    {
        int n, i, x1, x2, sum, y, ans[14000];
        MinHeap *H1;
        while(scanf("%d", &n) != EOF)
        {
            sum = 0;
            H1 = Creat(n);
            H1->Size = n;
            for(i = 1; i <= n; i++)
            {
                scanf("%d", &ans[i]);
            }
            qsort(&ans[1], n, sizeof(ans[1]), cmp);
            for(i = 1; i <= n; i++)
            {
                H1->Data[i] = ans[i];
            }
            GetBuild(H1);
            for(i = 0; i < n-1; i++)
            {
                x1 = Delete(H1);
                x2 = Delete(H1);
                y = x1 + x2;
                sum += y;
                Insert(H1, y);
            }
            printf("%d\n", sum);
        }
    }