1070 结绳 (25 分)C语言

给定一段一段的绳子，你需要把它们串成一条绳。每次串连的时候，是把两段绳子对折，再如下图所示套接在一起。这样得到的绳子又被当成是另一段绳子，可以再次对折去跟另一段绳子串连。每次串连后，原来两段绳子的长度就会减半。

给定 N 段绳子的长度，你需要找出它们能串成的绳子的最大长度。

输入格式：

每个输入包含 1 个测试用例。每个测试用例第 1 行给出正整数 N (2≤N≤10^4)；第 2 行给出 N 个正整数，即原始绳段的长度，数字间以空格分隔。所有整数都不超过10^4。

输出格式：

在一行中输出能够串成的绳子的最大长度。结果向下取整，即取为不超过最大长度的最近整数。

输入样例：

8

10 15 12 3 4 13 1 15

输出样例：

AC1，虽然会AC但多次提交会出现超时，所以是伪AC

#include <stdio.h>

int main(){

    int a,i,j;

    scanf("%d",&a);

    int m[a];

    for(i=0;i<a;i++){

        scanf("%d",&m[i]);

    }

    for(i=0;i<a;i++){//选择排序

        int min=i;

        for(j=i;j<a;j++){

            if(m[j]<m[min]){

                min=j;

            }

        }

        if(min != i){

            int num=m[i];

            m[i]=m[min];

            m[min]=num;

        }

    }

    double sum=m[0];//计算结果

    for(i=1;i<a;i++){

        sum=(sum+m[i])/2;

    }

    printf("%d",(int)sum);

    return 0;

}

AC2，采用快速排序省去一层for循环，时间复杂度极大降低，完美AC

#include<stdio.h>

int inc(const void *a, const void *b){

	return *(int *)a - *(int *)b;

 }

int main(){

    int N,i;

    scanf("%d",&N);

    int arr[N];

    for(i=0;i<N;i++){//输入数据

        scanf("%d",&arr[i]);

    }

    qsort(arr,N,sizeof(int), inc);//升序排序

    double total=arr[0];

    for(i=1;i<N;i++){

        total=(total+arr[i])/2;

    }

    printf("%d",(int)total);

    return 0;

}

巴特西

1070 结绳 (25 分)C语言

最新文章

热门文章