PAT甲级——A1125 Chain the Ropes【25】

Given some segments of rope, you are supposed to chain them into one rope. Each time you may only fold two segments into loops and chain them into one piece, as shown by the figure. The resulting chain will be treated as another segment of rope and can be folded again. After each chaining, the lengths of the original two segments will be halved.

Your job is to make the longest possible rope out of

Input Specification:

Each input file contains one test case. For each case, the first line gives a positive integer

Output Specification:

For each case, print in a line the length of the longest possible rope that can be made by the given segments. The result must be rounded to the nearest integer that is no greater than the maximum length.

Sample Input:

8
10 15 12 3 4 13 1 15

Sample Output:

分析：因为所有⻓度都要串在⼀起，每次都等于(旧的绳⼦⻓度+新的绳⼦⻓度)/2，所以越是早加⼊绳

⼦⻓度中的段，越要对折的次数多，所以既然希望绳⼦⻓度是最⻓的，就必须让⻓的段对折次数尽可

能的短。所以将所有段从⼩到⼤排序，然后从头到尾从⼩到⼤分别将每⼀段依次加⼊结绳的绳⼦中，

最后得到的结果才会是最⻓的结果～

 1 #include <iostream>
 2 #include <vector>
 3 #include <algorithm>
 4 #include <cmath>
 5 using namespace std;
 6 int main()
 7 {
 8     int n;
 9     double res;
10     cin >> n;
11     vector<double>v(n);
12     for (int i = 0; i < n; ++i)
13         cin >> v[i];
14     sort(v.begin(), v.end());
15     for (int i = 1; i < n; ++i)
16         v[i] = (v[i] + v[i - 1]) / 2.0;
17     cout << floor(v[n - 1]);//向下取整
18     return 0;
19 }