捡石子---贪心算法（huffman）

问题 E: 捡石子

时间限制: 1 Sec  内存限制: 128 MB
提交: 49  解决: 31
[ 提交][ 状态][ 讨论版]

题目描述

在一个圆形操场的四周摆放着 n堆石子。 现要将石子有次序地合并成一堆。 规定每次选2 堆石子合并成新的一堆，合并的费用为新的一堆石子数。试设计一个算法，计算出将 n堆石子合并成一堆的最小总费用。

输入

输入数据第1行有1个正整数 n（1≤n≤1000），表示有 n堆石子，每次选2堆石子合并。第2行有 n个整数， 分别表示每堆石子的个数（每堆石子的取值范围为[1,1000]） 。

输出

数据输出为一行， 表示对应输入的最小总费用。

样例输入

7
45 13 12 16 9 5 22

样例输出

313

提示

 

 中南大学计算机&软件复试QQ群552889929

 

[ 提交][ 状态]

 

 

#include <stdio.h>
#include <stdlib.h>
 
int cmp(const void *a,const void *b)
{
  return(*(int *)b-*(int *)a);  //实现的是降序排序
}
 
int main(int argc, char *argv[])
{
  //哈夫曼树的应用
  int n;
  int a[1005],i,j,sum;
  while(scanf("%d",&n)!=EOF){
      for(i=0;i<n;i++)
       scanf("%d",&a[i]);
 
     for(i=0,sum=0;i<n-1;i++)
     {
        qsort(a,n-i,sizeof(a[0]),cmp);
//        for(j=0;j<n;j++)
//            printf("%d ",a[j]);
//           printf("\n");
        a[n-2-i]=a[n-1-i]+a[n-2-i];//每次合并最小的两个
        if(n-2-i>-1)
        sum+=a[n-2-i];
//        if(n - 2 - i == 0) break;
//        printf("sum = %d\n", sum);
 
//         printf("sum = %d\n",sum);
     }
//     sum += (a[0] + a[1]);
     printf("%d\n",sum);
 
 
  }
 
  //system("PAUSE");
  return 0;
}
 
/**************************************************************
    Problem: 1187
    User: xiaxiany
    Language: C++
    Result: 正确
    Time:14 ms
    Memory:1084 kb
****************************************************************/