多元Huffman編碼

問題描述：在一個操場的四周擺放着n堆石子，現要将石子有次序地合并成一堆。規定每次至少選2堆至多選k堆石子合并成新的一堆，

合并的費用為新的一堆石子數。計算出将n堆石子合并成一堆的最大總費用和最小總費用。

算法設計：對于給定的n堆石子，計算合并成一堆的最大總費用和最小總費用。

資料輸入：檔案的第1行有2個正整數n和k，表示有n堆石子，每次至少選2堆至多選k堆石子合并。第2行有n個數，分别表示每堆石子的個數。

輸入示例：

7 3

45 13 12 16 9 5 22

輸出示例：

593 199

#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;
int i,stone[999];

int stonemax(int n,int k)
{
	priority_queue<int> q;
	//生成最大優先隊列
	for(i=0;i<n;i++)
	q.push(stone[i]);
	int sum=0,max=0;
	while(q.size()>2)
	//因為要求最大總費用，是以要求合并次數盡量多
	{
		sum=0;
		for(i=0;i<2;i++)
		{
			sum+=q.top();
			q.pop();
		}
		max+=sum;
		q.push(sum);
	}
	while(!q.empty())
	{
		max+=q.top();
		q.pop();
	}
	return max;
}

int stonemin(int n,int k)
{
	priority_queue<int,vector<int>,greater<int> > q;
	//生成最小優先隊列
	for(i=0;i<n;i++)
	q.push(stone[i]);
	int sum=0,min=0;
	while(q.size()>k)
	//因為要求最小總費用，是以要求合并次數盡量少
	{
		sum=0;
		for(i=0;i<k;i++)
		{
			sum+=q.top();
			q.pop();
		}
		min+=sum;
		q.push(sum);
	}
	while(!q.empty())
	{
		min+=q.top();
		q.pop();
	}
	return min;
}

int main()
{
    int n,k;
	cin>>n>>k;
    for(i=0; i<n; i++)
    cin>>stone[i];
    cout<<stonemax(n,k)<<endl;
    cout<<stonemin(n,k)<<endl;
    return 0;
}
           

運作截圖：