堆石子游戏的问题（多元Huffman编码）

问题描述：

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

编程任务：

对于给定n堆石子,编程计算合并成一堆的最大总费用和最小总费用。

Input
测试数据的第1 行有2个正整数n和k，表示有n堆石子，每次至少选2堆最多选k堆石子合并。第2行有n个数，分别表示每堆石子的个数。

Output
输出最大总费用和最小总费用，用一空格隔开，每个答案一行。

Sample Input
7 3
45 13 12 16 9 5 22

Sample Output
593 199

#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
bool cmp ( int a, int b )
{
	return a>b;
}
void Insert ( vector<int> &f, int pos, int value )
{
	for ( int i = f.size() - 1; i > pos; i-- )
	{
		f[i] = f[i - 1];
	}
	f[pos] = value;
}
int Find ( vector<int> f, int value )
{
	int pos = f.size() - 1;
	while ( pos >= 0 && f[pos] < value )
	{
		pos--;
	}
	return pos + 1;
}
int MaxNum ( vector<int> f )
{
	sort ( f.begin(), f.end() );
	int Max;
	Max = 0;
	while ( f.size() >= 2 )
	{
		int sum = f[f.size() - 1] + f[f.size() - 2];
		Max = Max + sum;
		f.resize ( f.size() - 1 );
		f[f.size() - 1] = sum;
	}
	return Max;
}
int MinNum ( vector<int> f, int len )
{
	sort ( f.begin(), f.end(), cmp );
	int Min;
	Min = 0;
	while ( f.size() >= len )
	{
		int sum = 0;
		for ( int i = f.size() - 1; i >= f.size() - len && i >= 0; i-- )
		{
			sum = sum + f[i];
		}
		Min = Min + sum;
		f.resize ( f.size() - len + 1 );
		if ( f.size() > len )
		{
			int pos = Find ( f, sum );
			Insert ( f, pos, sum );
		}
		else if ( f.size() != 1 )
		{
			f[f.size() - 1] = sum;
			for ( int i = 0; i < f.size(); i++ )
			{
				Min = Min + f[i];
			}
			break;
		}
		else
		{
			break;
		}
	}
	return Min;
}
bool run()
{
	int n, m;
	if ( ! ( cin >> n >> m ) ) return false;
	vector<int> f ( n );
	for ( int i = 0; i < n; i++ )
	{
		cin >> f[i];
	}
	int Max, Min;
	Max = MaxNum ( f );
	while ( f.size() % ( m - 1 ) != 1 )
	{
		f.push_back ( 0 );
	}
	Min = MinNum ( f, m );
	cout << Max << " " << Min << endl;
	return true;
}
int main()
{
	while ( run() );
	return 0;
}