/*
file name: KMerge.c
Description:K路归并,求最佳合并方案
*/
#include <stdio.h>
void Sort(int A[],int start,int end)
{
int i,j;
int s;
for(i=start;i<=end;i++){
for(j=start;j<=end;j++){
if(A[j]>A[j+1]){
int t;
t=A[j];
A[j]=A[j+1];
A[j+1]=t;
}
}
}
printf("nSorted List:t");
for(s=start;s<=end;s++)
printf("%dt",A[s]);
printf("n ");
}
void KMerge(int k,int A[],int length)
{
int sum;
int i;
int j;
int cur,t;
Sort(A,0,length-1);
cur=0;
while(1){
sum=0;
if(length-cur<k) // last time
t=length;
else
t=cur+k;
for(i=cur;i<t;i++){
printf("%dt",A[i]);
sum+=A[i];
}
cur=cur+k-1;
printf("n");
A[i-1]=sum;
Sort(A,i-1,length-1);
if(t==length) break; // last time ,break after execute!
}
}
void main(void)
{
int K[]={1,2,3,5,7,9,13};
int k=7;
KMerge(5,K,k);
printf("Result:%dn",K[k-1]);
}