最优合并问题
时间： 1ms 内存：64M
描述：
给定k 个排好序的序列s1 , s2,……, sk , 用2 路合并算法将这k 个序列合并成一个序列。假设所采用的2 路合并算法合并2 个长度分别为m和n的序列需要m + n -1次比较。试设计一个算法确定合并这个序列的最优合并顺序，使所需的总比较次数最少。
为了进行比较，还需要确定合并这个序列的最差合并顺序，使所需的总比较次数最多。
对于给定的k个待合并序列，计算最多比较次数和最少比较次数合并方案。
输入：
输入数据的第一行有1 个正整数k（k≤1000），表示有k个待合并序列。接下来的1 行中，有k个正整数，表示k个待合并序列的长度。
输出：
输出两个整数，中间用空格隔开，表示计算出的最多比较次数和最少比较次数。
示例输入：
4
5 12 11 2示例输出：
78 52提示：
参考答案（内存最优[1268]）：
#include<iostream>
#include<algorithm>
#include<vector>
#include<functional>
#include<queue>
using namespace std;
struct mycmp
{
bool operator()(const int &a,const int &b){
return a>b;
}
};
int main(){
priority_queue<int>x1;
priority_queue<int,vector<int>,mycmp>x2;
int k,i,sum=0,temp,num1,num2;
int a[2000];
cin>>k;
for(i=0;i<k;i++){
cin>>a[i];
x1.push(a[i]);
x2.push(a[i]);
}
sum=0;
temp=0;
while(temp!=k-1){
num1=x1.top();
x1.pop();
num2=x1.top();
x1.pop();
sum=sum+num1+num2-1;
x1.push(num1+num2);
temp++;
}
cout<<sum<<" ";
temp=0;
sum=0;
while(temp!=k-1){
num1=x2.top();
x2.pop();
num2=x2.top();
x2.pop();
sum=sum+num1+num2-1;
x2.push(num1+num2);
temp++;
}
cout<<sum;
return 0;
}
参考答案（时间最优[16]）：
#include<iostream>
#include<algorithm>
#include<vector>
#include<functional>
#include<queue>
using namespace std;
struct mycmp
{
bool operator()(const int &a,const int &b){
return a>b;
}
};
int main(){
priority_queue<int>x1;
priority_queue<int,vector<int>,mycmp>x2;
int k,i,sum=0,temp,num1,num2;
int a[2000];
cin>>k;
for(i=0;i<k;i++){
cin>>a[i];
x1.push(a[i]);
x2.push(a[i]);
}
sum=0;
temp=0;
while(temp!=k-1){
num1=x1.top();
x1.pop();
num2=x1.top();
x1.pop();
sum=sum+num1+num2-1;
x1.push(num1+num2);
temp++;
}
cout<<sum<<" ";
temp=0;
sum=0;
while(temp!=k-1){
num1=x2.top();
x2.pop();
num2=x2.top();
x2.pop();
sum=sum+num1+num2-1;
x2.push(num1+num2);
temp++;
}
cout<<sum;
return 0;
}
题目和答案均来自于互联网，仅供参考，如有问题请联系管理员修改或删除。