poj3253最小堆 Huffman 贪心

题目链接

Fence-Repair

题目描述(Description)

Fence Repair

题目大意：

Farmer John想修围墙，需要一堆木头。木头的数量N(1<=N<=20,000)，每段木头长度为Li(1<=Li<=50,000)。他买了一根无线长的木头，需要锯N-1次，花费的钱和据木头的长度一样。求FJ的最小花费。

输入

第一行：一个整数N，代表需要锯的木头数量

第二行-第N+1行：每段木头的长度

输出

一行：一个整数–最小花费

样例输入

3

8

5

8

样例输出

34

分析(Analysis)

数据存储

• 创建一个一维数组，存每根木头的长度，注意取值范围（可能有大数据），用C++中的long long更保险，否则会WA。
• 一个long long全局变量存结果ans。

算法

• 类似Huffman Tree，利用贪心算法，采用最小堆的结构，自下而上。每次从剩下的木头中选取长度最短的两根，计算二者之和，直到堆中只有一个元素；
• 一开始，把堆顶元素（最小值）赋值给node[0]，然后取堆的最尾元素插入堆顶，自上而下调整生成最小堆，取堆顶元素node[1]。此时node[0]和node[1]是最小的两个元素，计算二者之和，结果存于node[1]，ans加node[1]计算最小花费，再调整生成最小堆；
• 重复第二步，直到堆里只有一个元素，循环结束输出ans。

代码(Code)

#include<iostream>
using namespace std;
long long node[40020],ans;
/*从根节点开始向下调整*/
void down(long long x,long long size)
{
    long long i,j,tmp;
    tmp=node[x];
    i=x;
    j=2*i;
    while(j<=size)
    {
        if(j<size&&node[j]>node[j+1])
            j++;
        if(tmp>node[j])
        {
            node[i]=node[j];
            i=j;
            j=2*i;
        }
        else
                break;
    }
    node[i]=tmp;
}
/*从根节点开始插入元素建堆*/
void buildHeap(long long a[],long long size)
{
    long long i;
    for(i=size/2; i>0; i--)
    {
        down(i,size);
    }
}
int main()
{
    long long n,k;
    cin>>n;
    ans=0;
    for(k=1; k<=n; k++)
    {
        cin>>node[k];
    }
    buildHeap(node,n);
    while(n>1)
    {
        node[0]=node[1];/*取出堆顶元素*/
        node[1]=node[n--];/*把Node的最后一个元素放到堆顶*/
        down(1,n);/*向下调整建立最小堆*/
        node[1]+=node[0];
        ans+=node[1];
        down(1,n);
    }
    cout<<ans;
    return 0;
}