常用c 算法代码word版.doc

堆石子游戏的问题（多元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 = () - 1; i > pos; i--)
    {
        f[i] = f[i - 1];
    }
    f[pos] = value;
}
int Find(vector<int> f, int value)
{
    int pos = () - 1;
    while (pos >= 0 && f[pos] < value)
    {
        pos--;
    }
    return pos + 1;
}
int MaxNum(vector<int> f)
{
    sort((), ());
    int Max;
    Max = 0;
    while (() >= 2)
    {
        int sum = f[() - 1] + f[() - 2];
        Max = Max + sum;
        (() - 1);
        f[() - 1] = sum;
    }
    return Max;
}
int MinNum(vector<int> f, int len)
{
    sort((), (), cmp);
    int Min;
    Min = 0;
    while (() >= len)
    {
        int sum = 0;
        for (int i = () - 1; i >= () - len && i >= 0; i--)
        {
            sum = sum + f[i];
        }
        Min = Min + sum;
        (() - len + 1);
        if (() > len)
        {
            int pos = Find(f, sum);
            Insert(f, pos, sum);
        }
        else if (() != 1)
        {
            f[() - 1] = sum;
            for (int i = 0; i < (); 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);