最优合并问题
版权声明：本文为博主原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。
本文链接：https://blog.csdn.net/weixin_42449444/article/details/102945171
题目描述：
给定k个排好序的序列
s_{1},s_{2},...,s_{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;
}本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2019-11-06 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录