最优合并问题

最优合并问题

时间: 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;
}

题目和答案均来自于互联网,仅供参考,如有问题请联系管理员修改或删除。

点赞

发表评论

电子邮件地址不会被公开。必填项已用 * 标注