B

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题目，不能用作考。后面补了一个不用优先队列的方法，代码异常的多，不推荐。
(原来的代码有bug，虽然能AC，但无法解决n<k的情况，感谢热心网友NagiRingu)

#include <queue>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
#define maxn 10050
#define INF 0x3f3f3f3f

using namespace std;

int main(){
    int n, k, i, x, sum;
    long long MAX, MIN;
    MAX = MIN = 0;
    cin>> 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>> x;
        q1.push(x);
        q2.push(x);
    }
    while((int)q1.size() > 1){
        sum = q1.top();
        q1.pop();
        if(!q1.empty()){
            sum += q1.top();
            q1.pop();
        }
        MAX += sum;
        q1.push(sum);
    }
    if(n>k){
        x = n;
        while(x>k){
            x -= (k - 1);
        }
        for(i=x;i<k;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);
    }
    while(!q2.empty()){
        MIN += q2.top();
        q2.pop();
    }
    cout<<MAX<<' '<<MIN<<endl;
    return 0;
}

不使用优先队列，只能把堆的代码写出来。不过看老师给的参考答案，是可以使用优先队列的。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#define maxn 200050 //多元哈夫曼树最多会有2n-1个节点。

using namespace std;

//小顶堆建立过程。
struct heap_less{
    //数据存储
    long long data[maxn];
    //记录堆的大小。
    int num;
    //交换下标a，b的位置。
    void qswap(int a, int b){
        long long t;
        t = data[a];
        data[a] = data[b];
        data[b] = t;
    }
    //向下调整堆。
    void down(int i){
        int t, flag = 0;
        while(i*2 <= num && flag == 0){
            if(data[i] > data[i*2]){
                t = i * 2;
            }
            else
                t = i;
            if(i * 2 + 1 <= num){
                if(data[t] > data[i*2+1]){
                    t = i * 2 + 1;
                }
            }
            if (t != i){
                qswap(i, t);
                i = t;
            }
            else{
                flag = 1;
            }
        }
    }
    //向上调整堆。
    void up(int i){
        int t, flag = 0;
        while(i >= 1 && flag == 0){
            if(data[i] > data[i*2]){
                t = i * 2;
            }
            else
                t = i;
            if(i * 2 + 1 <= num){
                if(data[t] > data[i*2+1]){
                    t = i * 2 + 1;
                }
            }
            if (t != i){
                qswap(i, t);
                i = i / 2;
            }
            else{
                flag = 1;
            }
        }
    }
    //返回堆顶元素。
    int top(){
        return data[1];
    }
    //删除堆顶元素。
    void pop(){
        data[1] = data[num];
        down(1);
        num--;
    }
    //插入元素。
    void push(int x){
        num += 1;
        data[num] = x;
        up(num / 2);
    }
};

//大顶堆建立过程，该过程与小顶堆差别不大。
struct heap_gteater{
    long long data[maxn];
    int num;
    void qswap(int a, int b){
        long long t;
        t = data[a];
        data[a] = data[b];
        data[b] = t;
    }
    void down(int i){
        int t, flag = 0;
        while(i*2 <= num && flag == 0){
            if(data[i] < data[i*2]){
                t = i * 2;
            }
            else
                t = i;
            if(i * 2 + 1 <= num){
                if(data[t] < data[i*2+1]){
                    t = i * 2 + 1;
                }
            }
            if (t != i){
                qswap(i, t);
                i = t;
            }
            else{
                flag = 1;
            }
        }
    }
    void up(int i){
        int t, flag = 0;
        while(i >= 1 && flag == 0){
            if(data[i] < data[i*2]){
                t = i * 2;
            }
            else
                t = i;
            if(i * 2 + 1 <= num){
                if(data[t] < data[i*2+1]){
                    t = i * 2 + 1;
                }
            }
            if (t != i){
                qswap(i, t);
                i = i / 2;
            }
            else{
                flag = 1;
            }
        }
    }
    int top(){
        return data[1];
    }
    void pop(){
        data[1] = data[num];
        down(1);
        num--;
    }
    void push(int x){
        num += 1;
        data[num] = x;
        up(num / 2);
    }
};

int main()
{
    int n, k, i, x;
    heap_less h;
    heap_gteater h2;
    h.num = 0;
    scanf("%d%d",&n, &k);
    for(i=0; i<n; i++){
        scanf("%d",&x);
        h.push(x);
        h2.push(x);
    }
    int t = n;
    //如果节点数不能够建立一个完整的哈夫曼树，将节点用0补全。
    if(t > k){
        while(t > k){
            t -= (k  -1);
        }
        for(i=0; i<k-t; i++){
            h.push(0);
        }
    }
    //计算最小值，最小值是取最小值建立k元的哈夫曼树，并求值。（权值*路径长度）
    long long MIN, sum;
    MIN = 0;
    while(h.num >= k){
        sum = 0;
        for(i=0; i<k; i++){
            sum += h.top();
            h.pop();
        }
        MIN += sum;
        h.push(sum);
    }
    //计算最大值，最大值是取最大值建立2元哈夫曼常数，并求值。
    long long MAX;
    MAX = 0;
    while(h2.num >= 2){
        sum = 0;
        for(i=0; i<2; i++){
            sum += h2.top();
            h2.pop();
        }
        MAX += sum;
        h2.push(sum);
    }
    cout<<MAX<<" "<<MIN<<endl;
    return 0;
}