首页 > 其他 > 详细

PAT (Basic Level) 1070 结绳 (贪心)

时间:2021-08-24 20:22:09      阅读:9      评论:0      收藏:0      [点我收藏+]

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

技术分享图片

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

输入格式:

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

输出格式:

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

输入样例:

8
10 15 12 3 4 13 1 15
 
结尾无空行

输出样例:

14
 
结尾无空行
 
 
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        String s = reader.readLine();
        int N = Integer.parseInt(s);
        String s1 = reader.readLine();
        String[] s2 = s1.split(" ");
        int[] ints = new int[N];
        for (int i = 0; i < N; i++) {
            ints[i] = Integer.parseInt(s2[i]);
        }
        getLongest(ints);
    }

    public static void getLongest(int[] lens){
        Arrays.sort(lens);
        double sum = lens[0];
        for (int i = 1; i < lens.length; i++) {
            sum = (sum + lens[i]) / 2;
        }
        System.out.println((int)Math.floor(sum));
    }
}

  

PAT (Basic Level) 1070 结绳 (贪心)

原文:https://www.cnblogs.com/jasonXY/p/15181311.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!