多元Huffman编码问题

多元Huffman编码问题

Time Limit: 1000 ms Memory Limit: 65536 KiB

 

Problem 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

Sample Output

593 199

Hint

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

Source

 优化之后的：

#include<bits/stdc++.h>
using namespace std;
int n;
long long maxNum,minNum;
template<class T>
long long result(T q,int k,int flag){
    if(flag==1&&n>k){// 求最小的 更新
        int tmp=n;
        while(tmp>k) tmp=tmp-(k-1);
        for(int i=0;i<k-tmp;i++) q.push(0);
    }
    long long rst=0;
    while((int)q.size()>k){
        long long sum=0;//sum   k个 先后堆顶相加的值，合并之后，需要把sum 继续放进 优先队列里面 ，继续参与下面的合并
        for(int i=0;i<k;i++){
            sum+=q.top();//sum 加上堆顶的值
            q.pop();//同时需要把这个 堆顶的值删除
        }
        rst+=sum;//合并 费用 更新
        q.push(sum);//将合并的值  继续放进 优先队列 参与 下面的合并
    }
    while(!q.empty()){//合并 之后  优先队列（即堆） 里面还剩下 k  个 数据   这两堆合并 的费用 就是它们的两个的和
       rst+=q.top();//费用值  + 剩余的 两对 合并费用 结束
       q.pop();
    }
    return rst;//返回
}
int main()
{
    int k,data;
    priority_queue<long long> q;//默认 从大 到小
    priority_queue<long long,vector<long long>,greater<long long> > p;  //从小到大的顺序排列队列中的数据    cin>>n>>k;//输入n堆石子，每次至少选2 堆最多选k堆石子合并
    cin>>n>>k;
    for(int i=0;i<n;i++){
        cin>>data;
        q.push(data);
        p.push(data);
    }
    maxNum=result(q,2,0);//k =2  求最大 k=2
    minNum=result(p,k,1);// k堆
    cout<<maxNum<<" "<<minNum<<endl;
    return 0;
}

 

#include<bits/stdc++.h>
using namespace std;
long long data[100001];
int n;
long long maxNum,minNum;
// 两堆 合并   ，合并的费用为新的一堆的石子数
long long Max(int k){// 求最大的总费用:每次都要 找最大两堆  的进行合并
    priority_queue<long long> q;//使用 优先队列 ，优先队列排序方式为大顶堆 。堆顶的为最大。所以 求 最大费用，则为 每次的堆顶的值 进行k=2 次合并
    for(int i=0;i<n;i++) q.push(data[i]);//将数据 存入优先队列
    //最大费用  两两合并  最后的值 最优，所以 求最大k =2
    while((int)q.size()>k){//两两合并， 若 优先队列里面的值的个数  大于两个 ，那么 对数据 进行k=2次堆顶相加 求和
        long long sum=0;//sum  是两个 先后堆顶相加的值，合并之后，需要把sum 继续放进 优先队列里面 ，继续参与下面的合并
        for(int i=0;i<k;i++){
            sum+=q.top();//sum 加上堆顶的值
            q.pop();//同时需要把这个 堆顶的值删除
        }
        maxNum+=sum;//最大合并 费用 更新
        q.push(sum);//将合并的值  继续放进 优先队列 参与 下面的合并
    }
    while(!q.empty()){//合并 之后  优先队列（即堆） 里面还剩下 k =2 个 数据   这两堆合并 的费用 就是它们的两个的和
       maxNum+=q.top();//最大费用值  + 剩余的 两对 合并费用 结束
       q.pop();
    }
    return maxNum;//返回最大值
}
long long Min(int k){
    //优先队列 默认的是大顶堆，求最小费用 需要用到 小顶堆
    priority_queue<long long,vector<long long>,greater<long long> > q;//从小到大的顺序排列队列中的数据
    for(int i=0;i<n;i++)  q.push(data[i]);
    //算最小得分  最后留出k-1个数来合并才能得到最小值
   int tmp=n;//tmp 代表 n 堆 石子  //可一下合并，费用最小，
   //此判断 主要是 n 堆石子 大于 最大k堆 合并 ，要让前 x个数据 和k-x 个0  凑成k 堆，
   if(tmp>k){
         while(tmp>k){// tmp=n 能拆成 多少个  (k-1)  以及剩下tmp 个 数据
            tmp=tmp-(k-1);
         }
         //下面 的 k-tmp 个0 和 剩下的 tmp 个数据  合并成 一堆。 然后 和已经拆成的(k-1)一堆 进行合并 成新的一堆，如此 (k-1) (k-1) (k-1)....  继续合并
         for(int i=0;i<k-tmp;i++)//要让前面的k-tmp个数刚好能合并成1堆，需要加上k-m个零，用零来填充
            q.push(0);
   }
   while((int)q.size() > k){
     long long sum=0;
     for(int i=0;i<k;i++){
        sum+=q.top();
        q.pop();
     }// 个合并   合并之后的数据 放进 优先队列里面
     minNum+=sum;
     q.push(sum);
   }//当m<=k的时候，可以一下合并，所以 最小费用 就是 各个之和
   while(!q.empty()){//这里   minNum +剩余 的  k个  就是最小值；  相当于 minNum+ 最小的k个一次合并的值
    minNum+=q.top();
    q.pop();
   }
   return minNum;
}
int main()
{
    int k;
    maxNum=0;//初始化 最大 费用 0
    minNum=0;//初始化 最小 费用 0
    cin>>n>>k;//输入n堆石子，每次至少选2 堆最多选k堆石子合并
    for(int i=0;i<n;i++){
        cin>>data[i];//输入n 堆石子 数据
    }
    maxNum=Max(2);//k =2  求最大 k=2
    minNum=Min(k);//k 堆
    cout<<maxNum<<" "<<minNum<<endl;
    return 0;
}