问题
给定k个排好序的序列s1,s2,…,sk，用2路合并算法将这k个序列合并成一个序列。假设所采用的2路合并算法合并两个长度分别为m和n的序列需要m+n-1次比较。试设计一个算法确定合并这个序列的最优合并顺序，使所需要的总比较次数最少。
测试用例：
4（序列数） 5 12 11 2（序列中的元素数）
输出：
78（最差情况） 52（最优情况)
问题分析
需要求最优次数和最差次数，采用贪心求解。求最优次数时每次合并最短的两个，求最差时每次合并最长的两个。 仔细想想，这题和霍夫曼编码就是一个事，只不过霍夫曼需要求合并树的路径，这个比他简单点。
代码
#include<iostream>
using namespace std;
int Print(int m[],int n)
{
for(int i=0;i<n;i++)
{
cout<<m[i]<<" ";
}
cout<<endl;
}
int sort(int num[],int n,int flag)
{
int t;
for(int i=0;i<n;i++)
{
for(int j=i;j<n;j++)
{
if((num[i]<num[j]&&flag==1)||(num[i]>num[j]&&flag==0))
{
t=num[i];
num[i]=num[j];
num[j]=t;
}
}
}
}
int MinMerge(int num[],int n)
{
int t=n;
sort(num,n,1);
n=n-1;
int sum=0;
while(n>0)
{
num[n-1]=num[n-1]+num[n];
n--;
sum+=num[n];
sort(num,n+1,1);
}
printf("%d\n",sum);
sum-=(t-1);
return sum;
}
int MaxMerge(int num[],int n)
{
sort(num,n,0);
Print(num,n);
int t=n;
n=n-1;
int sum=0;
while(n>0)
{
num[n-1]=num[n-1]+num[n];
n--;
sum+=num[n];
sort(num,n+1,0);
}
printf("%d\n",sum);
sum-=(t-1);
return sum;
}
int main()
{
int n;
cin>>n;
int num[n];
int num2[n];
for(int i=0;i<n;i++)
{
cin>>num[i];
num2[i]=num[i];
}
int min=MinMerge(num,n);
int max=MaxMerge(num2,n);
cout<<"最差时间"<<max<<endl;
cout<<"最优时间"<<min<<endl;
}
结果：
