PAT乙级1070 || 结绳（详解，C/C++示例，测试点分析）

Posted on In

结绳

题目描述

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

给定 N 段绳子的长度，你需要找出它们能串成的绳子的最大长度。

输入格式

每个输入包含 1 个测试用例。每个测试用例第 1 行给出正整数 N (2≤N≤$10^4$)；第 2 行给出 N 个正整数，即原始绳段的长度，数字间以空格分隔。所有整数都不超过$10^4$。

输出格式

在一行中输出能够串成的绳子的最大长度。结果向下取整，即取为不超过最大长度的最近整数。

输入样例

1
2
8
10 15 12 3 4 13 1 15

输出样例

1
14

问题解决

解题思想

本题虽然是25分，如果想到了使最终串联绳子的长度达到最长的方法论，实现将是非常简单的过程。此题的原理类似于数据结构中的哈夫曼编码原理（与之相反），要想最后达到最长，应尽可能的让较长的绳子最后再参与串连，较短的绳子先串连。

因此，对输入的各段绳子按绳长进行升序排序，从短到长逐个取绳子进行串连，最后得到的绳长即为N个绳子串连后得到的最大长度。

知识拓展

vector容器的使用：

vector的定义
1
2
vector <int> vi;	//定义一个整型vi,可以理解为可变长度的数组。
vector <double> vi;	//double型的vi
vector的访问
  1. 可以像数组一样通过下标访问
  2. 也可以通过迭代器访问
vector的用法
1
2
3
vi.push_back(i)；	//在vi尾部添加元素i
vi.begin();	//vi首元素地址
vi.end();	//vi尾元素地址的下一个地址

其它相关vector的内容可参看相关C++标准模板库(STL)的书籍。

代码示例（C/C++）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
vector <double> vi;
int main() {
    int n;
    scanf("%d", &n);
    for(int i = 0; i < n; i++) {
        double tmp;
        scanf("%lf", &tmp);
        vi.push_back(tmp);  //vi末尾添加一个元素
    }
    sort(vi.begin(), vi.end());	//升序排序
    double maxlen = (vi[0] + vi[1]) / 2;    //前两个绳子串联后的长度
    for(int i = 2; i < n; i++) {    //从短到长依次串连
        maxlen = (maxlen + vi[i]) / 2;
    }
    printf("%d", (int)maxlen);
    return 0;
}

题目来源：PAT乙级1070
作者：CHEN, Yue
单位：浙江大学

稀罕作者