1125. Chain the Ropes.md

【PAT A-1125、PAT B-1070】Chain the Ropes、结绳

题意概述

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

输入输出格式

输入第 1 行给出正整数 N。第 2 行给出 N 个正整数，即原始绳段的长度，数字间以空格分隔。所有整数都不超过${10}^4$。

输出能串成的绳子的最大长度。

数据规模

$$2\le N\le{10}^4$$

算法设计

由于每次串连的时候都需要将两根绳子对折，所以越是先串连的绳子对折次数越多，因此为了保证最后的长度最长，串连的绳子中长度越长的就应该越晚串连。于是我们只需要按长度将给定的绳子从小到大排序，按题目描述逐个绳子进行串连，得到的长度必然是最长的。这里我们使用的贪心策略就是：先串连长度短的绳子，再串连长度长的绳子。

注意点

1. 当串联第一根绳子时不用对折。
2. 为了保证结果的精度，最好用 double 储存输入的绳子长度，最后对结果进行向下取整，这样在对折取半时就不会丧失精度。

C++代码

#include <bits/stdc++.h>
using namespace std;
using gg = long long;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    gg n;
    cin >> n;
    vector<double> v(n);
    for (int i = 0; i < n; ++i)
        cin >> v[i];
    sort(v.begin(), v.end());
    cout << floor(accumulate(v.begin() + 1, v.end(), v[0],
                             [](double a, double b) { return (a + b) / 2; }));
    return 0;
}