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

代码示例：

#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;
}