1.实践题目
7-1 最优合并问题 （100 分）
题目来源：王晓东《算法设计与分析》
给定k 个排好序的序列, 用 2 路合并算法将这k 个序列合并成一个序列。 假设所采用的 2 路合并算法合并 2 个长度分别为m和n的序列需要m+n-1 次比较。试设 计一个算法确定合并这个序列的最优合并顺序，使所需的总比较次数最少。 为了进行比较，还需要确定合并这个序列的最差合并顺序，使所需的总比较次数最多。
输入样例:
4
5 12 11 2
输出样例:
78 52
2.问题描述
将几个序列合并成一个序列，序列的比较次数的计算方式是序列长度分别为m和n的序列为m+n-1 次。序列的最差合并顺序就是先合并长的再合并短的，序列的最优合并顺序应优先合并最短的。
3.算法描述
Min_sum=(2+5-1)+(2+5+11-1)+(2+5+11+12-1)=52
Max_sum=(12+11-1)+(12+11+5-1)+(12+11+5+2-1)=78
先将序列长度进行排序，计算最优合并顺序的是先合并最短的两个序列，用min_sum记录比较次数，min_sum=a[min_index]+a[min_index+1]-1，用a[min_index]存放合并之后的那个序列，同时将a[min_index+1]置为0，min_index++;再重新排序得到新的列表。（重新排序的原因是因为合并之后的序列有可能比原先的序列都大，这个有点类似哈夫曼树）。以上重复n-1次。
计算最差合并顺序则只需要排序一次就可以，合并两个最长的序列得到的序列也自然是最长的。用max_sum记录比较次数，从排序好数组的数组最后开始循环，计算比较次数，max_sum=a[k-1]+a[k-2]-1。
#include<iostream> #include<algorithm> using namespace std; int main(){ int n; cin>>n; int a[n],b[n]; for (int i=0;i<n;i++){ cin>>a[i]; b[i]=a[i]; } sort(a,a+n); int min_sum=0,min_index=0; while (min_index<n-1){ min_sum=min_sum+a[min_index]+a[min_index+1]-1; a[min_index]=a[min_index]+a[min_index+1]; a[min_index+1]=0; min_index++; sort(a,a+n); } sort(b,b+n); int max_sum=0,max_temp=b[n-1]; for (int i=n-2;i>=0;i--){ max_temp+=b[i]; max_sum=max_sum+max_temp-1; //cout<<i<<"--"<<max_sum<<endl; } cout<<max_sum<<" "<<min_sum; return 0; }
4.算法时间及空间复杂度分析（要有分析过程）
时间复杂度：直接进行排序是O(n*logn),计算min_sum要进行n次排序，所以为O(n^2logn)。
空间复杂度：两个数组的大小，O(n)。
5.心得体会（对本次实践收获及疑惑进行总结）
第一题是我们最后做的题，当时晓冰几乎做出来了，但是一开始总是显示段错误，我们于是修改了数组的长度定义，提交后对了一半，例子对了，可是另一个测试点没有对。我们才注意到开始算法不妥的地方，在找最优解时，我们先把数组排序，然后从小到大的加，却忽略了前面的和数大于后面的值的情况，在做修改后终于做了出来。