qq_40229278
Chris_kxt
2018-04-25 07:50
采纳率: 71.4%
浏览 2.1k

C++语言编程 运用贪心算法的方法

给定k 个排好序的序列, 用 2 路合并算法将这k 个序列合并成一个序列。 假设所采用的 2 路合并算法合并 2 个长度分别为m和n的序列需要m+n-1 次比较。试设 计一个算法确定合并这个序列的最优合并顺序,使所需的总比较次数最少。 为了进行比较,还需要确定合并这个序列的最差合并顺序,使所需的总比较次数最多。

输入格式:
第一行有 1 个正整数k,表示有 k个待合并序列。 第二行有 k个正整数,表示 k个待合并序列的长度。

输出格式:
输出最多比较次数和最少比较次数。

输入样例:
在这里给出一组输入。例如:

4
5 12 11 2
输出样例:
在这里给出相应的输出。例如:

78 52


#include
using namespace std;

  • 点赞
  • 写回答
  • 关注问题
  • 收藏
  • 邀请回答

4条回答 默认 最新

  • weixin_40768609
    weixin_40768609 2018-04-26 09:32
    已采纳

    #include
    using namespace std;
    void print(int *a,int len)
    {
    int i=0;
    for(;i cout cout }
    void exchange(int*a,int *b)
    {
    int t=*a;
    *a=*b;
    *b=t;
    }
    int partition(int *a,int left,int right)
    {
    int key=a[right];
    int i=left-1;
    int j=left;
    while(j {
    if(a[j] {
    ++i;
    exchange(&a[i],&a[j]);
    }
    ++j;
    }
    exchange(&a[i+1],&a[right]);
    return i+1;
    }
    void q_sort(int *a,int left,int right)
    {
    if(left>=right)
    return;
    int q=partition(a,left,right);
    q_sort(a,left,q-1);
    q_sort(a,q+1,right);
    }
    void find_k_max(int *left,int *right,int k_max)
    {
    if(right-left<k_max||k_max<0)
    {
    cout<<"error"<<endl;
    return;
    }
    int *t=left;
    int tm[right-left+1];
    int i=0;
    for(;i<right-left+1;++i)
    tm[i]=*t++;
    q_sort(&tm[0],0,right-left);
    //print(&tm[0],right-left+1);
    t=tm+(right-left);
    while(k_max)
    {
    --t;
    --k_max;
    }
    cout<<*t<<endl;

    }
    int main()
    {
    int n;
    cin>>n;
    int a[n];
    int i;
    for(i=0;i cin>>a[i];
    //q_sort(a,0,n-1);
    //print(a,n);
    int m;
    cin>>m;
    int j;
    int left[m];
    int right[m];
    int k_max[m];

    for(j=0;j {
    cin>>left[j];
    cin>>right[j];
    cin>>k_max[j];
    }
    for(j=0;j<m;++j)
    find_k_max(a+left[j]-1,a+right[j]-1,k_max[j]-1);

    return 0;
    }

    点赞 评论
  • caozhy
     #include <stdio.h>  
    #include <algorithm>  
    
    using namespace std;  
    
    int n;  
    int cmp(int a,int b)  
    {  
        return a>b;  
    }  
    
    int minsum(int a[],int m)  
    {  
        int b[n];  
        int sum=0;  
        for(int i=0;i<n;i++)  
        {  
            b[i]=a[i];  
        }  
        while(m>1)  
        {  
            sort(b,b+m);  
            b[0]=b[0]+b[1];  
            sum+=b[0];  
            for(int i=1;i<m-1;i++)  
            {  
                b[i]=b[i+1];  
            }  
            m--;  
        }  
        return sum-n+1;  
    }   
    
    
    int maxsum(int a[],int m)  
    {  
        int b[n];  
        int sum=0;  
        for(int i=0;i<n;i++)  
        {  
            b[i]=a[i];  
        }  
        while(m>1)  
        {  
            sort(b,b+m,cmp);  
            b[0]=b[0]+b[1];  
            sum+=b[0];  
            for(int i=1;i<m-1;i++)  
            {  
                b[i]=b[i+1];  
            }  
            m--;  
        }  
        return sum-n+1;   
    }   
    
    int main()  
    {  
    
        int a[100];  
        scanf("%d",&n);  
        for(int i=0;i<n;i++)  
        {  
            scanf("%d",&a[i]);  
        }  
    
        printf("min:%d\n",minsum(a,n));  
        printf("max:%d\n",maxsum(a,n));  
    }  
    
    点赞 评论
  • caozhy
    点赞 评论
  • garfiledcn
    garfiledcn 2018-05-16 11:14

    可以考虑一下哈夫曼编码的原则和计算方式

    点赞 评论

相关推荐