文章目录

• 一【题目难度】
• 二【题目编号】
• 三【题目描述】
• 四【题目示例】
• 五【解题思路】
• 六【最终得分】
• 七【代码实现】
• 八【提交结果】

一【题目难度】

• 乙级

二【题目编号】

• 1070 结绳 (25 分)

三【题目描述】

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

四【题目示例】

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

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

• 输入样例：
  8
  10 15 12 3 4 13 1 15

• 输出样例：
  14

五【解题思路】

• 整体思路比较简单，利用贪心的思想，让每次损失的最小（因为要除以2），所以当一个数越小的时候损失的越小，所以尽量先用小的数计算，所以对数组从小到大排序，然后依次计算即可，注意要用 f l o a t float float类型接收结果，因为会有小数，若用 i n t int int类型可能会导致损失精度，最后输出的时候别忘了向下取整

六【最终得分】

• 25分

七【代码实现】

#include<stdio.h>
#include<stdlib.h>

int cmp_1070_KnottedRope(const void *a,const void *b)
{
    return *(int*)a > *(int*)b;
}

int main()
{
    int n;
    scanf("%d",&n);
    int *nums = (int*)malloc(sizeof(int)*n);
    for(int i = 0;i<n;i++)
    {
        scanf("%d",&nums[i]);
    }
    qsort(nums,n,sizeof(int),cmp_1070_KnottedRope);
    float res = nums[0];
    for(int i = 1;i<n;i++)
    {
        res = (res + nums[i]) / 2;
    }
    printf("%d",(int)res);
    return 0;
}

八【提交结果】