linux typeScript Markdown编辑器 selenium printing 如何做网络营销推广 routes Plupload vue绑定点击事件 vue表单提交 ppt视频教程下载 jquery拼接字符串 pip环境变量配置 python文件读取 javaswitch java中string java迭代器 获取当前时间java java方法的调用 python开发实例 php网络编程 shutil 两表关联查询 编辑软件 js关闭当前页面 亚索刀光 算法笔记 编程电子书 梦想世界科举答案 qq空间自动点赞 a1474 华为工具箱 kms工具 js绑定事件的方法 街机roms下载 ps文字旋转任意角度 sql列转行 图层蒙版抠图 关闭redis pathping
当前位置: 首页 > 学习教程  > 编程语言

基础实验4-2.7 修理牧场 (25 分)

2021/2/13 20:24:51 文章标签: 测试文章如有侵权请发送至邮箱809451989@qq.com投诉后文章立即删除

农夫要修理牧场的一段栅栏,他测量了栅栏,发现需要N块木头,每块木头长度为整数L ​i ​​ 个长度单位,于是他购买了一条很长的、能锯成N块的木头,即该木头的长度是L ​i ​​ 的总和。 但是农夫自己没有锯子&#xff0…

农夫要修理牧场的一段栅栏,他测量了栅栏,发现需要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
#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>
#define MINDATA -1
typedef int ElementType;

ElementType W = 0;

typedef struct HTNode *HuffmanTree;
struct HTNode
{
    int length;
    HuffmanTree Left;
    HuffmanTree Right;
};

typedef struct HNode *Heap;
struct HNode
{
    ElementType * Data;               
    int Size;
    int Capacity;
};
typedef Heap MinHeap;

MinHeap CreateHeap(int MaxSize)
{
    MinHeap H = (MinHeap)malloc(sizeof(struct HNode));
    H ->Size = 0;
    H ->Capacity = MaxSize;
    H ->Data = (ElementType*)malloc(sizeof(ElementType)*(MaxSize+1));
    /*for (int i =0; i<=MaxSize ; i++)
    {
        H->Data[i]->Left = H->Data[i]->Right = NULL;
    }*/
    H ->Data[0] = MINDATA;
    return H;
}

bool IsFull(MinHeap H)
{
    return H->Size == H->Capacity;
}

bool Insert(MinHeap H, ElementType X)
{
    if(IsFull(H))
        return false;
    int i = ++H->Size;
    for ( ; H->Data[i/2]  > X ; i/=2)
        H ->Data[i]  = H ->Data[i/2] ;
    H ->Data[i]  = X;
    return true;
}

/*bool IsEmpty(MinHeap H)
{
    return H->Size == 0;
}*/

HuffmanTree DeleteMin(MinHeap H)
{
    int Parent, Child;
    ElementType  X;
    HuffmanTree MinItem = (HuffmanTree)malloc(sizeof(struct HTNode));
    MinItem->length = H->Data[1];

    /*if(IsEmpty(H))
        exit(-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(H->Data[Child]  >= X)
            break;
        else
            H->Data[Parent]  = H->Data[Child]  ;
    }

    H ->Data[Parent]  = X;
    return MinItem;
}


HuffmanTree Huffman(MinHeap H)
{
    int i, N;
    HuffmanTree T;

    N = H->Size;
    for( i=1; i<N; i++)
    {
        T = (HuffmanTree)malloc(sizeof(struct HTNode));
        T ->Left = DeleteMin(H);
        T ->Right = DeleteMin(H);
        T ->length = T->Left->length + T->Right->length;
        W += T->length;
        Insert(H, T->length); 
    }
    return DeleteMin(H);
}

int main()
{
    int N, i, X;
    scanf("%d",&N);
    MinHeap H = CreateHeap(N);
    for ( i=1; i<=N ; i++ )
    {
        scanf("%d",&X);
        Insert(H, X);
    }
    HuffmanTree root = Huffman(H);
    printf("%d",W);
    return 0;
}

1.这道题最后要得到的,并非是Huffman最后删除的那个节点的权值。而是之前每次新结合出来的节点的和。才是要花的钱。

2.堆的insert()和buildheap()其实可以互相替换。

void PercDown(MinHeap H, int p)
{
    int  Parent, Child;
    ElementType 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(H->Data[Child]  >= X)
            break;
        else
            H->Data[Parent]  = H->Data[Child] ;
    }
    H ->Data[Parent]  = X;
}

void BuildHeap(MinHeap H)
{
    int i ;
    for ( i=H->Size/2 ; i>0 ; i-- )
        PercDown(H, i);
}

本文链接: http://www.dtmao.cc/news_show_700478.shtml

附件下载

相关教程

    暂无相关的数据...

共有条评论 网友评论

验证码: 看不清楚?