题目

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

给定N段绳?的?度，你需要找出它们能串成的绳?的最??度。
输?格式：
每个输?包含1个测试?例。每个测试?例第1?给出正整数N (2<=N<=10^4)；第2?给出N个正整数，即原始绳段的?度，数字间以空格分隔。所有整数都不超过104。
输出格式：
在??中输出能够串成的绳?的最??度。结果向下取整，即取为不超过最??度的最近整数。
输?样例：
8
10 15 12 3 4 13 1 15
输出样例：
14

题目分析

已知一系列线段，两两衔接长度折半，求所有线段组成最长绳子的长度

解题思路

1. 贪心算法：取当前最短的两个线段衔接，长度折半会最小
2. 对所有线段长度进行升序排序
3. 依次取两个线段进行衔接

易错点

1. 长度累加变量，不能初始化为0，因为arr[0]要和arr[1]结合折叠，而不是0和arr[0]折叠

Code

Code 01

#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;
int main(int argc,char *argv[]) {
    int N;
    scanf("%d",&N);
    int arr[N]={0};
    for(int i=0; i<N; i++) {
        scanf("%d", &arr[i]);
    }
    sort(arr,arr+N);
//  double L=0.0; //不能从0开始，因为arr[0]要和arr[1]结合折叠，而不是0和arr[0]折叠 
    double L=arr[0];
    for(int i=0; i<N; i++) {
        L=(L+arr[i])/2.0;
    }
    printf("%d",(int)floor(L));
    return 0;
}

PAT Basic 1070 结绳(25) [排序，贪?]

原文：https://www.cnblogs.com/houzm/p/12245703.html