37、数据结构与算法实战:堆石子

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期。算法很巧妙,之前学习《数据结构》课程的时候也确实没有想得这么深入,学到了!

版权声明:本文不是「本站」原创文章,版权归原作者所有 | 原文地址: