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

Question

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

Answer 1

#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;
}

Answer 2

 #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));  
}  

Answer 3

这里还有一个java的
http://www.pudn.com/downloads722/sourcecode/java/detail2892287.html

Answer 4

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