POJ3253 Fence Repair （二叉堆）

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

題意：給你幾根木板，讓你連接起來，每次連接花費為兩根長度之和。連接所有的木板，最後最小的花費是多少。

這個題目用貪心即可。即，每次的取兩根最小的，花費最少，最後花費就最少。

本題目可以用二叉堆的最關鍵就在於二叉堆的定義：

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

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

通過一維數組最後一個添加或者刪除，進行調整。

1.一般堆解法：

時間消耗：

#include 
#include 
#include 
#include 

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 
#include 
#include 
#include 

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;
}

沒有寫出來，方法就幾個， 沒有獲取彈出堆首元素的方法。如果你會的話，請告訴我= =