最优合并问题
给定k个排好序的序列s1,s2,…,sk，用2路合并算法将这k个序列合并成一个序列。假设所采用的2路合并算法合并两个长度分别为m和n的序列需要m+n-1次比较。试设计一个算法确定合并这个序列的最优合并顺序，使所需要的总比较次数最少。
测试用例： 4（序列数）
5 12 11 2（序列中的元素数）
输出： 78（最差情况） 52（最优情况)
分析:
次数最多:总是最长的两个先合并
次数最少：总是最短的两个先合并
#include<stdio.h>
#include<stdlib.h>
int cmp1(const void *a,const void *b){
return *(int *)a-*(int *)b;//升序
}
int cmp2(const void *a,const void *b){
return *(int *)b-*(int *)a;//降序
}
int main(){
int n;//序列数
scanf("%d",&n);
int p[n],p1[n];
int times=0;
for(int i=0;i<n;i++){
scanf("%d",&p[i]);
p1[i]=p[i];
}
for(int i=0;i<n-1;i++){
qsort(p,n,sizeof(int),cmp1);
p[0]=p[0]+p[1];
times+=p[0]-1;
p[1]=100000;
}
printf("最少次数：%d\n",times);
times=0;
for(int i=0;i<n-1;i++){
qsort(p1,n,sizeof(int),cmp2);
p1[0]=p1[0]+p1[1];
times+=p1[0]-1;
p1[1]=0;
}
printf("最多次数：%d\n",times);
return 0;
}
运行截图
