P1070 结绳
2024-08-31 06:26:59
P1070 结绳
转跳点:
070 结绳 (25分)
给定一段一段的绳子,你需要把它们串成一条绳。每次串连的时候,是把两段绳子对折,再如下图所示套接在一起。这样得到的绳子又被当成是另一段绳子,可以再次对折去跟另一段绳子串连。每次串连后,原来两段绳子的长度就会减半。
给定 N 段绳子的长度,你需要找出它们能串成的绳子的最大长度。
输入格式:
每个输入包含 1 个测试用例。每个测试用例第 1 行给出正整数 N (2≤N≤104);第 2 行给出 N 个正整数,即原始绳段的长度,数字间以空格分隔。所有整数都不超过104。
输出格式:
在一行中输出能够串成的绳子的最大长度。结果向下取整,即取为不超过最大长度的最近整数。
输入样例:
8
10 15 12 3 4 13 1 15
输出样例:
14
通过率0.41的题目没啥好说的,这道题可以用计数排序来化简时间复杂度,还有就是sum的初始值应该是arr[0],每次都得挑选出最短前缀,让我想起了哈夫曼编码……
//AC代码(qsort):
#include <stdio.h>
#include <stdlib.h> int compare(const void *a, const void *b) { return (*(int *)a) > (*(int *)b); } int main(void)
{
int n; scanf("%d", &n);
int arr[n]; for (size_t i = 0; i < n; i++)
{
scanf("%d", arr + i);
} qsort(arr, n, sizeof(arr[0]), compare); int sum = arr[0];
for (size_t i = 1; i < n; i++)
{
sum += arr[i];
sum /= 2;
} printf("%d\n", sum); return 0;
}
AC代码(计数排序):
#include <stdio.h>
#include <stdlib.h> int main(void)
{
int n, index, sum = 0;
int arr[10005] = {0}; scanf("%d", &n); for (size_t i = 0; i < n; i++)
{
scanf("%d", &index);
arr[index]++;
} size_t i = -1;
while (0 == arr[++i] && i < 10001)
;
sum += i; while (i++ < 10001)
{
while (arr[i]--)
{
sum += i;
sum /= 2;
}
} printf("%d\n", sum); return 0;
}
PTA不易,诸君共勉!
最新文章
- CentOS RedHat YUM 源扩展补充(32位、64位均有)
- java环境配置为1.7jdk为什么cmd java -version查看版本是1.8
- 【BZOJ-1911】特别行动队 DP + 斜率优化
- 跨越多台haproxy 跳转
- 让Docker功能更强大的10个开源工具
- 27 自定义View小结
- C# &; JAVA:读写文件
- Linux下查看设设置时间date命令
- Linux下NFS的搭建与配置
- html页面出现&;#65279,影响布局
- AJax知识介绍
- TCP/IP协议(3):数据链路层
- Visual Studio 中的 Office 和 SharePoint 开发
- mysql常见的错误码
- Mac PHPStorm快捷键总结
- Echarts 的悬浮框tooltip显示自定义格式化
- 【我的Android进阶之旅】 解决bug: Expected file scheme in URI: content://downloads/my_downloads/12
- Linux设置虚拟内存-创建和启用Swap交换区
- Android(java)学习笔记95:Android运行时异常";Binary XML file line # : Error inflating class";
- thinkphp5开发restful-api接口学习 教程视频 接口文档
热门文章
- springboot 打包成jar
- office 格式定义
- [PHP]PHP中申明 declare(strict_types=1)的作用
- Ubuntu开启端口(持久化)
- HTML5中改变了哪些东西?
- 解决:Field xxMapper in xx.service.impl.xxServiceImpl required a bean of type &#39;xx.mapper.xxMapper&#39;
- 解决安装PyMySQL一直停在Building wheels for collected package:cryptography, cffi, pycparser的问题
- MFC加载图片
- C++结构体struct与C语⾔结构体和C++引⽤&;与传值的区别
- Linux centosVMware Tomcat介绍、安装jdk、安装Tomcat