Description
在一片沙滩上摆放着n堆石子。 现要将石子有次序地合并成一堆。 每次任选2堆石子合并成新的一堆，合并的费用为新的一堆石子数。试设计一个算法，计算出将n堆石子合并成一堆的最小总费用。
Input
输入数据第1行有1个正整数 n（1≤n≤100000），表示有 n堆石子，每次选2堆石子合并。第2行有 n个整数， 分别表示每堆石子的个数（每堆石子的取值范围为[1,1000]） 。
Output
数据输出为一行， 表示对应输入的最小总费用。
Sample Input
7
45 13 12 16 9 5 22
Sample Output
313
参考程序（C语言实现）
#include <stdio.h>
#define PILE_AMOUNT 100000
#define MAX_WEIGHT 1000
int table[MAX_WEIGHT+5]={
0};
long long sum[PILE_AMOUNT+10]={
0};
long long s=0;
int main()
{
int n,i,tmp,front=0,rear=0;
scanf("%d",&n);
for(i=0;i<n;i++)
{
scanf("%d",&tmp);
table[tmp]+=1;
}
if(n==1)
{
//只有一堆石头，无需合并
printf("%d\n",tmp);
}
else
{
int first=-1,second=-1,i=1;
while(1)
{
while(first==-1 || second==-1)
{
//查找table表，取出质量最少的两堆石头：first second
if(table[i]==0)
{
i++;
if(i>MAX_WEIGHT)
break;
else
continue;
}
else
{
if(first==-1)
{
first=i;
table[i]--;
continue;
}
if(second==-1)
{
second=i;
table[i]--;
break;
}
}
}
if(i>MAX_WEIGHT)
{
//table表已全部遍历完，只可能first有值，second是-1；或者first、 second全是-1
if(first!=-1)
{
//最小的两个元素first 和队头
sum[rear++]=sum[front]+first;
front++;
}
while(rear-front!=1)
{
sum[rear++]=sum[front]+sum[front+1];
front+=2;
}
break;
}
else
{
if(rear-front==0)
{
//队列为空
sum[rear++]=first+second;
first=-1;
second=-1;
}
else if(rear-front==1)
{
//队列只有一个元素
long long fr=sum[front];//读取队头，暂时先不出队
if(fr>=second)
{
//最小的两个元素是first和second
sum[rear++]=first+second;
first=-1;
second=-1;
}
else
{
front++;//取出队头
sum[rear++]=first+fr;
table[second]++;//将second放回
second=-1;
first=-1;
}
}
else
{
//rear-front>=2 队列至少有2个元素
long long fr1=sum[front],fr2=sum[front+1];
if(fr1<=first && fr2>first || fr1>first && fr1<=second)
{
//最小的两个元素是first、fr1
sum[rear++]=fr1+first;
front++;
table[second]++;//将second放回
second=-1;
first=-1;
}
else if(fr1>second)
{
//最小的两个元素是first，second
sum[rear++]=first+second;
first=-1;
second=-1;
}
else if(fr2<=first)
{
//最小的两个元素是fr1,fr2
sum[rear++]=fr1+fr2;
front+=2;
table[second]++;
table[first]++;
i=first;//i 回退
second=-1;
first=-1;
}
}
}
}
for(i=0;i<rear;i++)
{
s+=sum[i];
}
printf("%lld\n",s);
}
return 0;
}
分析：本题使用的是贪心算法设计策略，石子合并的次数是n-1次，如果每次都是选取质量最少的两堆石子，那么可以得到将所有石子合并为一堆的最小花费即全局最优。因此程序的整体流程本质上是和哈夫曼树构建过程一致的。
一种很容易想到的方法是：先将所有重量降序排序，选出质量最少的两堆，合并，并将这两个数从原数组中移除，再将合并结果插入到数组中保持有序，随后再重复地进行选择、合并、移除、插入过程直至数组为空。分析这个过程的时间复杂度：整体排序，时间复杂度O(nlgn)，每取两个合并再插入，时间复杂度O(n)，但是插入过程要执行n-1
次，所以整体时间复杂度是O(n2)，这也是传统的哈夫曼树构建时的时间复杂度。但本题如果使用该算法，会超时。
本人参考了一篇论文，学到了一种构建哈弗曼树的高效算法。核心思想上，因为每次只需找出数组中最小的两个数，合并的结果插入在哪个位置其实并不需要特别关心，完全可以省略掉插入环节。
算法流程如下（摘自一篇论文）：
在这个算法中，具体实现时，可以把b抽象为队列（存放的全部是合并的中间结果，如果需要取出数据参与合并运算，则出队；将合并结果入队。因每次的合并结果是不断增大的，所以队头到队尾依次递增，也是有序的）。巧妙的是，在有序数组a中按顺序逐个取出数后不会将结果加到a中而是存到一个新的队列里，这样免去了插入环节，也保证a中剩余的始终是没有参与合并运算的；队列b中通过出队、入队操作，保存的是没有参与运算的。同时需要注意，每一次选取的两个最小数或者全部来自于a数组，或者全部来自队列中队头两个（如果有的话）元素，或者一个来自于a数组，一个来自于队头，只有这个三种情况。每次合并需要比较多个数的大小。
可以看到，这样的算法流程只需排序一次，遍历数组a一次，顺便需要在队列上进行出队、入队操作。总的时间复杂度是O(nlgn)
回到这道题，考虑到石子的重量是1~1000,所以如果要进一步优化算法，可以借助“计数排序”的原理，开1000个空间的统计表，下标是石子的重量，数组的值就是这种重量的石头出现的次数，然后按照下标的顺序查表，这样就相当于排好序了，时间复杂度可以降到O(n)。只是这样编程实现有点复杂。
这道题使用的算法参考了一篇论文，《构建赫夫曼树的高效算法》，张雷振、陈圆圆，计算机时代2010年第1期。算法很巧妙，之前学习《数据结构》课程的时候也确实没有想得这么深入，学到了！
版权声明：本文不是「本站」原创文章，版权归原作者所有 | 原文地址: