PTA乙级题 1070. 结绳(25)

【题目链接】

还是读懂题目意思就简单，这里自己定义了一个快排函数。

#include<stdio.h>
int a[10000];
int qsort(int left,int right)
{
    int i,j,t,temp; 
    if(left>right) 
    return 0; 
    temp=a[left]; //temp中存的就是基准数 
    i=left; 
    j=right; 
    while(i!=j) 
    { 
        /*顺序很重要，要先从右边开始找 ，读者不妨 想想为什么一定要先从右边开始找*/
        while(a[j]>=temp && i<j) 
            j--;
        while(a[i]<=temp && i<j) 
            i++; 
        //此处一定要注意加上i<j
        //交换两个数在数组中的位置 
        if(i<j) 
        { 
            t=a[i]; 
            a[i]=a[j]; 
            a[j]=t; 
        } 
    } 
    //最终将基准数归位 
    a[left]=a[i]; 
    a[i]=temp;                              
    qsort(left,i-1);//继续处理左边的，这里是一个递归的过程 
    qsort(i+1,right);//继续处理右边的 ，这里是一个递归的过程 
} 
int main()
{
    int i,n,sum;
    scanf("%d",&n);
    for (i=0;i<n;i++)
    scanf("%d",a+i);
    qsort(0,n-1);
    sum=a[0];
    for (i=1;i<n;i++)
    sum=(sum+a[i])/2;
    printf("%d",sum);
}