题目:

         有n件重量不同的物品，现要求耗费最少的体力将它们合并成一堆。每一次合并可以把两堆物品合并成一堆，消耗的体力等于两堆物品的重量之和。

输入： 第一行输入物品个数n，以下n行依次输入各物品重量。

输出： 输出耗费的最小体力。

 

　　用堆排序每次将两个权值最小的结点取出，从结点集中删除并将合并后的结点加入节点集合，合并后的结点权值为这两个被删除结点的权值之和，累加新结点的权值。重复计算直到只剩随后一个结点为止，最后所累加的权值和即为所求解。

 

#include<iostream>

using namespace std ;

int a[100] ;

void heap(int s, int n){            //调整堆,使其始终为小根堆

    int i, j = 1, k = a[s], max = 0 ;

    while(j!=max){

        i = a[s] ;

        j = max ;

        if(2*s<=n)

            if(a[s*2]<i){

                i = a[s*2] ;

                j = s * 2 ;

            }

        if(s*2+1<=n)

            if(a[s*2+1]<i){

                i = a[s*2+1] ;

                j = s*2+1 ;

            }

        if(j!=max){

            a[s] = i ;

            s = j ;

        }

        a[s] = k ;

    }

}

void swap(int i, int j){        //交换a[i], a[j]的值

    int temp = a[i] ;

    a[i] = a[j] ;

    a[j] = temp ;

}

int main(){

    int n, i ;

    cin >> n ;

    for(i=1; i<=n; i++)

        cin >> a[i] ;

    for(i=n/2; i>0; i--)        //构建小根堆

        heap(i, n) ;

    int sum = 0 ;

    while(n!=1){                //只剩一个结点时退出

        swap(1, n) ;

        heap(1, n-1) ;

        n -- ;

        swap(1, n) ;

        heap(1, n-1) ;

        a[n] = a[n] + a[n+1] ;  //将当前最小的两个结点权值累加，做为新结点的权值

        sum += a[n] ;

    }

    cout << sum ;

}