题解 P1090 【合并果子】

hulaquan · 2016-05-16 16:13:56 · 题解

//每次都选最小的两个，求和，得到一个新数，再重复

//第一次，我们用快排得到最小的两个数 
//如何使这个新数有序，我们观察到原有序列是有序的，所以使用插入排序 
//测试数据  3 1 5 4 6 2
//1 2 3 4 5 6    
//  3 3 4 5 6    +3
//    4 5 6 6    +6
//      6 6 9    +9
//         9 12   +12
//            21   +21 
#include <stdio.h>
//从小到大 
void quickSort(int a[],int left,int right){
    int i,j,temp,value;
    if(left>=right) return ;
    i=left;
    j=right;
    value=a[(i+j)/2];a[(i+j)/2]=a[i];a[i]=value;
    while(i<j){
        while(i<j&&a[j]>=value)j--;
        a[i]=a[j];
        while(i<j&&a[i]<=value)i++;
        a[j]=a[i];
    }
    a[i]=value;
    quickSort(a,left,i-1);
    quickSort(a,i+1,right);
}
//插入排序 
void insertSort(int a[],int n,int key){
    int pos,i;
    pos=0;
    while(key>a[pos]&&pos<n)pos++;
    if(pos==0){
        a[-1]=key;
    }else{
        i=0;
        while(i<=pos){
            a[i-1]=a[i];
            i++;    
        }
        a[pos-1]=key;
    }
}
int main()
{
    int i,n,sum,key;
    int a[10005];
    scanf("%d",&n);
    for(i=0;i<n;i++)
        scanf("%d",&a[i]);
    quickSort(a,0,n-1);
    sum=0;
    for(i=0;i<n-2;i++){
        key=a[i]+a[i+1];
        sum+=key;
        //待排序的a数组，从位置a+2+i开始，长度为n-i-2 
        insertSort(a+2+i,n-i-2,key);
    }
    printf("%d",sum+a[n-2]+a[n-1]);
    return 0;
}