/*
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]);
}