PAT A1125 Chain the Ropes(C++)

PAT甲级目录 | PAT乙级目录

题目描述

原题地址:A1125 Chain the Ropes
中文版:B1070 结绳

解题思路

每次都将两段绳子对折,再相连,会使得先连接上的绳子在最后占据的长度最短。所以要使得最终绳子最长,应该先连接长度最较短的,再连接长度较长的。

易错点

  • 首先将绳子初始长度设置为第一段绳子,循环开始时直接连接第二段。
    • 若初始长度为 0,则第一段绳子将会多除以 2 .

也许陌生的知识点

  • sort(S, S + n, cmp);
    • 排序函数,实现 [first, last) 范围内的排序,可以自定义排序策略 cmp 函数
    • 不带 cmp 参数的 sort 函数实现从小到大排序
    • 所需头文件: algorithm

代码示例:

1
2
3
4
5
6
7
8
9
10
11
12
13
#include <cstdio>
#include <algorithm>
using namespace std;
int main(){
int N, r[10010];
scanf("%d", &N);
for(int i = 0; i < N; i++){ scanf("%d", &r[i]); }
sort(r, r + N);
double ans = r[0];
for(int i = 1; i < N; i++) ans = (ans + r[i]) / 2;
printf("%d\n", (int)ans);
return 0;
}