guff.cpp

在一个操场的四周摆放着n 堆石子。现要将石子有次序地合并成一堆。规定在合并过程 中最多可以有m(k)次选k 堆石子合并成新的一堆

#include<iostream>
#include<fstream.h>

ifstream inf("input.txt");
ofstream outf("output.txt");

int n;
bool viable; //问题是否有解
int* stones; //石堆的石子个数
int* times; //允许k堆合并的次数
int* merger; //合并方案

class MinHeap//构造小顶堆
{
private:
	int size,MaxSize;//size为堆中元素个数，maxsize为堆容量
	int* node;//堆中元素表
public:
	MinHeap(int DefaultSize=20)//默认初始化大小为20
	{
		size=0;
		MaxSize=DefaultSize;
		node=new int[MaxSize+1];
	}
	void Initialize(int array[],int ArraySize,int HeapSize)//建立堆
	{
		delete[] node; //释放node空间
		node=array;
		size=ArraySize;
		MaxSize=HeapSize;
		for (int i=size/2;i>=1;i--)
		{
			int y=node[i];
			int j=2*i;
			while (j<=size)
			{
				if(j<size && node[j]>node[j+1])
				{
					j++;
				}
				if (y<=node[j])
				{
					break;
				}
				node[j/2]=node[j];
				j*=2;
			}
			node[j/2]=y;
		}
	}
	MinHeap& insert(int x)//插入一个数
	{
       int i=++size;
	   while (i!=1 && x<node[i/2])
	   {
		   node[i]=node[i/2];
		   i/=2;
	   }
	   node[i]=x;
	   return *this;
	}
	MinHeap& deleteMin(int &x)//删除并返回最小值
	{
		x=node[1];
		int y=node[size--];
		int i=1,ci=2;
		while (ci<=size)
		{
			if (ci<size && node[ci]>node[ci+1])
			{
				ci++;
			}
			if (y<=node[ci])
			{
				break;
			}
			node[i]=node[ci];
			i=ci;
			ci*=2;
		}
		node[i]=y;
		return *this;
	}
};


void SetMerger(int MerSum,int index)//构造merger数组的值,即可行的合并方案
{
	if(MerSum==n-1)//找到了解决方案，返回。
	{	
		viable=true;
		return;
	}
	else if(MerSum>n-1 || index==n-1 )//超过了合并堆数，向上返回
	{
		return;
	}        
	int Mertimes=times[n-index];//取出当前能合并的最大堆数能合并的次数。
	int Maxtime=(n-1-MerSum)/(n-1-index);//Maxtime取得利用这个能合并的最大堆数，能进行几次合并；n-1-index为当前能合并的最大堆数；
	if (Mertimes>Maxtime)//取小值，得到利用这个最大对数进行合并的次数。
	{
		Mertimes=Maxtime;
	}
	for (int i=Mertimes;i>=0;i--)
	{
		merger[n-index]=i;
		MerSum+=i*(n-index-1);
		SetMerger(MerSum,index+1);
		if(viable)
			return;
		MerSum-=i*(n-index-1);	

	}
}	
int MinCost()//利用merger[]提供的方案，原则是：1）小的先合并；2）每次从小顶堆中取出最小的i个数进行merger[i]次合并。
{
	MinHeap* h=new MinHeap();
	h->Initialize(stones,n,n);//建立小顶堆
	int sum=0;
	for (int i=2;i<=n;i++)//遍历merger[]
	{
		for (int k=1;k<=merger[i];k++)//进行merger[i]次合并；
		{
			int subsum=0;
			for (int j=1;j<=i;j++)//每次取i个最小元素合并；
			{
				int x;
				h->deleteMin(x);//从堆中取出最小元素。
				subsum+=x;
			}
			sum+=subsum;
			h->insert(subsum);//将合并后的石堆放入堆中。
		}
	}
	return sum;
}

void main()
{
	viable=false;
	inf >> n;//有几个石子堆
	stones=new int[n+1];
	times=new int[n+1];
	merger=new int[n+1];
	int i;
	for(i=1;i<=n;i++)
		inf>>stones[i];
	for(i=2;i<=n;i++)
		inf>>times[i];
	for(i=0;i<=n;i++)
		merger[i]=0;
	SetMerger(0,0);//寻找可能的最优合并方案，既设置最优merger[]。
	if (!viable)
	{
		outf<< "No solution!";			
	}
	else//利用SetMerger(0,0)得到的merger[]来组织元素合并
	{
		outf<< MinCost();			
	}	
}