【PAT (Basic Level) Practice】——【贪心】1070 结绳

文章目录

一【题目难度】

  • 乙级

二【题目编号】

  • 1070 结绳 (25 分)

三【题目描述】

  • 给定一段一段的绳子,你需要把它们串成一条绳。每次串连的时候,是把两段绳子对折,再如下图所示套接在一起。这样得到的绳子又被当成是另一段绳子,可以再次对折去跟另一段绳子串连。每次串连后,原来两段绳子的长度就会减半。
    【PAT (Basic Level) Practice】——【贪心】1070 结绳
    给定 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;
}

八【提交结果】

【PAT (Basic Level) Practice】——【贪心】1070 结绳

上一篇:如何按间隔大小把相邻数据分组


下一篇:学习笔记 网络流