问题描述

给定k个排好序的序列s1,s2,…,sk,用2路合并算法将这k个序列合并成一个序列。假设采用的2路合并算法合并2个长度分别为m和n的序列需要m+n-1次比较。试设计一个算法确定合并这个序列的最优合并顺序，使所需的总比较次数最少。
为了进行比较，还需要确定合并这个序列的最差合并顺序，使所需的总比较次数最多。

输出输出示例

数据输入：第1行有1个正整数k，表示有k个待合并序列。接下来的1行中，有k个正整数，表示k个待合并序列的长度。
结果输出：输出最多的比较次数和最小的比较次数。

输入：

4
5 12 11 2

输出：

78 52

算法分析

个问题我们可以用贪心策略来思考，每次选出两个长度最小的序列进行合并，选到最后肯定是总比较次数最小。最多的比较次数就是每次选出两个长度最大的序列进行合并。选长度最大和最小的序列可以用优先队列实现，由于c++stl中定义的优先队列默认是大顶堆，所以当我们想用小顶堆时就把堆中元素取反再进队列，出堆之后再取反。最后就可以计算出最多的比较次数和最小的比较次数。

代码

amax表示最多的比较次数，amin表示最小的比较次数。QU1设置为小顶堆，QU2设置为大顶堆。

#include<bits/stdc++.h>

using namespace std;

int n, amax, amin;

priority_queue<int> QU1, QU2;

int main(){
    cin >> n;
    while(n --){
        int x;
        cin >> x;
        QU1.push(-x);       //输出-x转化为小顶堆
        QU2.push(x);        //大顶堆
    }
    while(QU1.size() > 1){  //输出最小的两个数
        int a = -QU1.top();
        QU1.pop();
        int b = -QU1.top();
        QU1.pop();
        amin += a + b - 1;
        QU1.push(-a - b);   //把两个数的和再放入堆中
    }

    while(QU2.size() > 1){  //输出最大的两个数
        int a = QU2.top();
        QU2.pop();
        int b = QU2.top();
        QU2.pop();
        amax += a + b - 1;  //把两个数的和再放入堆中
        QU2.push(a + b);
    }

    cout << amax << " " << amin;
    return 0;
}