首页 > 其他分享 >PAT Basic 1070. 结绳

PAT Basic 1070. 结绳

时间:2023-04-05 11:34:18浏览次数:41  
标签:PAT int 绳子 1070 对折 Basic 长度

PAT Basic 1070. 结绳

1. 题目描述:

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

PAT Basic 1070

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

2. 输入格式:

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

3. 输出格式:

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

4. 输入样例:

8
10 15 12 3 4 13 1 15

5. 输出样例:

14

6. 性能要求:

Code Size Limit
16 KB
Time Limit
200 ms
Memory Limit
64 MB

思路:

绳子每串联一次长度就会减半,为了获得最大长度的绳子,较长的绳子应该尽可能少串联,这样损失的长度最少。先把绳子按长度递增排序,然后按照规律计算最终长度即可。

以\(N=5\)为例,假设按长度递增的绳子为\(a,b,c,d,e\),这里前两根绳子会对折\(N-1\)次,后续绳子的对折次数按顺序从\(N-2\)次递减。这里使用库函数qsort对绳子排序,使用floor进行向下取整。

My Code:

#include <stdio.h>
#include <stdlib.h> // malloc header, qsort header
#include <math.h> // floor header

int cmp(const void *p1, const void *p2);

int main(void)
{
    int ropeCount = 0;
    int *pRope = NULL;
    int i=0;
    double sum = 0.0;
    int res = 0;
    int factor = 0;
    
    scanf("%d", &ropeCount);
    pRope = (int *)malloc(sizeof(int) * ropeCount);
    
    for(i=0; i<ropeCount; ++i)
    {
        scanf("%d", pRope+i);
    }
    qsort(pRope, ropeCount, sizeof(int), cmp); // ascending order
    
    sum += pRope[0] * pow(0.5, ropeCount-1);
    sum += pRope[1] * pow(0.5, ropeCount-1);
    
    factor = ropeCount - 1;
    for(i=2; i<ropeCount; ++i)
    {
        --factor;
        sum += pRope[i] * pow(0.5, factor);
    }
    
    res = floor(sum);
    printf("%d\n", res);
    
//     for(i=0; i<ropeCount; ++i) // test output
//     {
//         printf("%d ", pRope[i]);
//     }
    
    
    free(pRope);
    return 0;
}

int cmp(const void *p1, const void *p2)
{
    return (*(int *)p1 - *(int *)p2);
}

标签:PAT,int,绳子,1070,对折,Basic,长度
From: https://www.cnblogs.com/tacticKing/p/17289022.html

相关文章

  • PAT Basic 1069. 微博转发抽奖
    PATBasic1069.微博转发抽奖1.题目描述:小明PAT考了满分,高兴之余决定发起微博转发抽奖活动,从转发的网友中按顺序每隔N个人就发出一个红包。请你编写程序帮助他确定中奖名单。2.输入格式:输入第一行给出三个正整数M(≤1000)、N和S,分别是转发的总量、小明决定的中奖间隔......
  • 【PAT乙】1080 MOOC期终成绩 (25分)
    problem1080MOOC期终成绩(25分)对于在中国大学MOOC(http://www.icourse163.org/)学习“数据结构”课程的学生,想要获得一张合格证书,必须首先获得不少于200分的在线编程作业分,然后总评获得不少于60分(满分100)。总评成绩的计算公式为G=(Gmid−term×40%+Gfinal×60%),如果Gmi......
  • nav_msgs/Path
    nav_msgs/Path消息用于描述一条路径信息。可以多设置几个坐标点,小车就会依次经过这些点。下面是消息格式其中包含了header和poses两个部分:header:这个消息的头部信息,包括序列号seq、时间戳stamp和参考坐标系frame_id。poses:一组路径点位姿信息,包含多个header和pose;每一个位姿......
  • 解析: xpath
    解析_1_xpath基本使用<!DOCTYPEhtml><htmllang="en"><head><metacharset="UTF-8"/><title>Title</title></head><body><ul><liid="l1"class="c1&q......
  • Cannot download Packages/expat-devel-2.2.5-4.el8.x86_64.rpm: All mirrors were tr
    错误原因从错误可以看出无法下载此包,因为所有镜像都已经尝试过了。可能是因为该软件包不再可用或镜像服务器当前不可用。解决方法因为CENTOS8自带rpm,所以就不需要下载rpm了。检查依赖包是否安装:(这步可忽略)rpm-qmakeautoconfautomakecmakeperl-CPANlibcurl-develli......
  • PAT Basic 1067. 试密码
    PATBasic1067.试密码1.题目描述:当你试图登录某个系统却忘了密码时,系统一般只会允许你尝试有限多次,当超出允许次数时,账号就会被锁死。本题就请你实现这个小功能。2.输入格式:输入在第一行给出一个密码(长度不超过20的、不包含空格、Tab、回车的非空字符串)和一个正整数N(≤......
  • powershell path
    https://github.com/ThePoShWolf/Utilities/blob/master/Misc/Set-PathVariable.ps1<#.SYNOPSIS ModifythePATHenvironmentvariable..DESCRIPTION Set-PathVariableallowsyoutoaddorremovepathstoyourPATHvariableatthespecifiedscopewithlogic......
  • PAT Basic 1066. 图像过滤
    PATBasic1066.图像过滤1.题目描述:图像过滤是把图像中不重要的像素都染成背景色,使得重要部分被凸显出来。现给定一幅黑白图像,要求你将灰度值位于某指定区间内的所有像素颜色都用一种指定的颜色替换。2.输入格式:输入在第一行给出一幅图像的分辨率,即两个正整数 \(M\) 和 ......
  • PAT甲级真题1020.树的遍历
    翻译和代码思路:Acwing一个二叉树,树中每个节点的权值互不相同。现在给出它的后序遍历和中序遍历,请你输出它的层序遍历。输入格式第一行包含整数N,表示二叉树的节点数。第二行包含N个整数,表示二叉树的后序遍历。第三行包含N个整数,表示二叉树的中序遍历。输出格式输出一......
  • PAT Basic 1064. 朋友数
    PATBasic1064.朋友数1.题目描述:如果两个整数各位数字的和是一样的,则被称为是“朋友数”,而那个公共的和就是它们的“朋友证号”。例如123和51就是朋友数,因为1+2+3=5+1=6,而6就是它们的朋友证号。给定一些整数,要求你统计一下它们中有多少个不同的朋友证号。2.输入......