B - 多元Huffman编码问题

Description

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

Input

输入数据的第1 行有2 个正整数n和k（n≤100000，k≤10000），表示有n堆石子，每次至少选2 堆最多选k堆石子合并。第2 行有n个数（每个数均不超过 100），分别表示每堆石子的个数。

Output

将计算出的最大总费用和最小总费用输出，两个整数之间用空格分开。

Sample

Input

7 3
45 13 12 16 9 5 22

Output

593 199

Hint

请注意数据范围是否可能爆 int。

题解：

涉及哈夫曼问题，首先哈夫曼树是每次选择最大或最小的点搭建的，而大顶堆或小顶堆刚好能满足这个要求，因此，可以用堆来解哈夫曼问题。
c++中优先队列便是一个堆，所以可以用优先队列解题。
由于数据过大，所以int会WA改用long long int。
在建立多元哈夫曼时，如果当前节点不足以建立一个K元的哈夫曼（有一个节点的子节点数量小于K），则需要补零来完善。
每次选择最大值来建立二元哈夫曼树，会得到最费力的值。
注：因为考试无法使用优先队列，因此该代码只能用于AC题目，不能用作考试，之后会补一个不用优先队列的。

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <queue>

using namespace std;

int maxn = 100050;

int main(){
    int n, k;
    long long i, MAX, MIN, sum;
    long long a[maxn];
    scanf("%d%d",&n,&k);
    priority_queue<long long> q1;
    priority_queue<long long, vector<long long>, greater<long long> >q2;
    for(i=0;i<n;i++){
        cin>>a[i];
        q1.push(a[i]);
        q2.push(a[i]);
    }
    MAX = 0;
    while(q1.size() >= 2){
        sum = q1.top();
        q1.pop();
        sum += q1.top();
        q1.pop();
        MAX += sum;
        q1.push(sum);
    }
    MIN = 0;
    int t = n;
    if(t>k){
        while(t>k){
            t -= (k - 1);
        }
        for(i=0; i<k - t; i++)
            q2.push(0);
    }
    while((int)q2.size() >= k){
        sum = 0;
        for(i=0; i<k; i++){
            sum += q2.top();
            q2.pop();
        }
        MIN += sum;
        q2.push(sum);
    }
    if(q2.size() != 1){
        while(!q2.empty()){
        MIN += q2.top();
        q2.pop();
        }
    }
    printf("%lld %lld\n",MAX,MIN);
    return 0;
}

B - 多元Huffman编码问题

原文：https://www.cnblogs.com/luoxiaoyi/p/13848464.html