贪心算法最优合并问题

---

---

最优合并问题

给定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;
}

运行截图