文章目录
一【题目难度】
- 乙级
二【题目编号】
- 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;
}