麦芽雪冷萃

题目描述：

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

输入描述：

第一行有1个正整数k，表示有k个待合并序列。接下来的1行中，有k个正整数，表示k个待合并序列的长度。

输出描述：

输出最多比较次数和最少比较次数。

输入样例：

4
5 12 11 2

输出样例：

78 52

解题思路：

贪心算法，最优合并时要求m+n-1尽可能的小，所以最优合并其实就是将升序排列的序列中的最小俩个值不断合并，直到序列中只有一个元素为止，这样就能求得最多比较次数。最差合并相反，降序排列的最大俩个值不断合并，直到序列中只有一个元素为止，这样就能求得最少比较次数。我是用vector的erase和push_back来模拟合并的过程的。

代码：

#include <bits/stdc++.h>
using namespace std;
#define Up(i,a,b) for(int i = a; i <= b; i++)
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    int k;  //k个待合并序列
    cin >> k;
    vector<int> v;
    Up(i,1,k)
    {
        int _;
        cin >> _;
        v.push_back(_);
    }
    sort(v.begin(),v.end());    //升序排列
    int maxans = 0,minans = 0;     //最多比较次数maxans,最少比较次数minans
    vector<int> v1 = v;     //copy一份vector的数据,v1求最大比较次数,v求最小比较次数
    sort(v1.begin(),v1.end(),greater<int>());   //降序排列
    while(v.size() != 1)    //直到vector中只有一个元素为止
    {
        //求最少比较次数
        int m = v[0], n = v[1];
        minans += m+n-1;
        vector<int>::iterator it = find(v.begin(),v.end(),m);
        v.erase(it,it+2);   //合并俩个数
        v.push_back(m+n);
        sort(v.begin(),v.end());
        //求最多比较次数
        m = v1[0], n = v1[1];
        maxans += m+n-1;
        it = find(v1.begin(),v1.end(),m);
        v1.erase(it,it+2);
        v1.push_back(m+n);
        sort(v1.begin(),v1.end(),greater<int>());
    }
    cout << maxans << " " << minans << endl;
    return 0;
}