POJ3253 Fence Repair （二叉堆）

本文出自：http://blog.csdn.net/svitter

题意：给你几根木板，让你连接起来，每次连接花费为两根长度之和。连接所有的木板，最后最小的花费是多少。

这个题目用贪心即可。即，每次的取两根最小的，花费最少，最后花费就最少。

本题目可以用二叉堆的最关键就在于二叉堆的定义：

大根堆：上面的比下面的大；

小根堆：上面的比下面的小；

通过一维数组最后一个添加或者删除，进行调整。

1.一般堆解法：

时间消耗：

#include <iostream>
#include <stdio.h>
#include <string.h>
#include <algorithm>

using namespace std;

__int64 a[20010];
int m, n;

void heap(int m)
{
    int t;
    while(m * 2 <= n)//有子堆
    {
        m = m * 2;
        if(m < n && a[m] > a[m+1]) // 较大的子堆
        {
            m++;
        }
        if(a[m] < a[m / 2]) //
        {
            t = a[m];
            a[m] = a[m/2];
            a[m/2] = t;
        }
        else
            break;
    }
}

void push_heap()
{
    int i = n;
    __int64 x = a[n];
    while(i > 1 && a[i/2] > x)
    {
        a[i] = a[i/2];
        i /= 2;
    }
    a[i] = x;
}

void pop_heap()
{
    __int64 x;
    //swap top.root
    x = a[1];
    a[1] = a[n];
    a[n] = x;

    n--;
    heap(1);
}

void make_heap()
{
    int i;
    for(i = n / 2; i > 0; i --)//从n/2构建即可
    {
        heap(i);
    }
}

void ace()
{
    int i;
    __int64 cur0, cur1, cur, sum;
    while(~scanf("%d", &n))
    {
        for(i = 1; i <= n; i++)
        {
            scanf("%I64d", &a[i]);
        }
        make_heap();
        sum = 0;
        while(n != 1)
        {
            pop_heap();
            cur0 = a[n+1];
            pop_heap();
            cur1 = a[n+1];
            cur = cur0 + cur1;
            sum += cur;
            a[++n] = cur;
            push_heap();
        }
        printf("%I64d\n", sum);
    }
}

int main()
{
    ace();
    return 0;
}

时间消耗：

#include <iostream>
#include <stdio.h>
#include <string.h>
#include <algorithm>

using namespace std;

__int64 a[20010];
int m, n;


void ace()
{
    int i;
    __int64 cur0, cur1, cur, sum;
    while(~scanf("%d", &n))
    {
        for(i = 1; i <= n; i++)
        {
            scanf("%I64d", &a[i]);
        }
        make_heap();
        sum = 0;
        while(n != 1)
        {
            pop_heap();
            cur0 = a[n+1];
            pop_heap();
            cur1 = a[n+1];
            cur = cur0 + cur1;
            sum += cur;
            a[++n] = cur;
            push_heap();
        }
        printf("%I64d\n", sum);
    }
}

int main()
{
    ace();
    return 0;
}

没有写出来，方法就几个， 没有获取弹出堆首元素的方法。如果你会的话，请告诉我= =

POJ3253 Fence Repair （二叉堆）,布布扣,bubuko.com

POJ3253 Fence Repair （二叉堆）

原文：http://blog.csdn.net/svitter/article/details/24554285