1125. Chain the Ropes (25)

我就是我 2022-05-28 12:05 113阅读 0赞

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.

![na_ol5x4jo19qm.jpg][]

Your job is to make the longest possible rope out of N given segments.

**Input Specification:**

Each input file contains one test case. For each case, the first line gives a positive integer N (2 <= N <= 104). Then N positive integer lengths of the segments are given in the next line, separated by spaces. All the integers are no more than 104.

**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:**

14

--------------------

题目大意：

代码：

#include<stdio.h>
    #include<algorithm>
    #include<vector>
    using namespace std;
    vector<int> v;
    int main()
    {
        int i,j,n,m,k,t;
        scanf("%d",&n);
        for(i=0;i<n;i++)
        {
           scanf("%d",&m);
            v.push_back(m);
        }
        sort(v.begin(),v.end());
        int result=v[0];
        for(i=1;i<n;i++)
        {
            result=(result+v[i])/2;
        }
        printf("%d\n",result);
        return 0;
    }

[na_ol5x4jo19qm.jpg]: http://nos.patest.cn/na_ol5x4jo19qm.jpg

发表评论取消回复

表情：

评论列表（有 0 条评论，113人围观）

还没有评论，来说两句吧...

相关阅读

相关 1125 Chain the Ropes (25point(s)) 贪心

题目题目链接思路给很多段绳子，你要做的是将这些绳子串成一条绳子: 每次从绳子中取两段，每段绳子对折后套在一起，所以绳子的长度会减半，求最终能串成的绳子最大长度；为了使最终...

矫情吗；*/ 2024年05月08日 06:12/ 0 赞/ 29 阅读

相关 1125 Chain the Ropes (25 分)

iven some segments of rope, you are supposed to chain them into one rope. Each time y...

痛定思痛。/ 2024年04月18日 10:39/ 0 赞/ 26 阅读

相关 1125day7

1.SVM算法的优缺点优点：可以优先解决高维特征的分类和回归问题无需依赖全体样本，只依赖支持向量有大量的核技巧可以使用，从而应对线性不可分问题适合样本量

分手后的思念是犯贱/ 2022年12月24日 04:58/ 0 赞/ 117 阅读

相关 1106. Lowest Price in Supply Chain (25)

A supply chain is a network of retailers（零售商）, distributors（经销商）, and suppliers（供应商）-- e

短命女/ 2022年05月30日 07:08/ 0 赞/ 76 阅读

相关 1090. Highest Price in Supply Chain (25)

A supply chain is a network of retailers（零售商）, distributors（经销商）, and suppliers（供应商）-- e

野性酷女/ 2022年05月30日 03:53/ 0 赞/ 111 阅读

相关 1094. The Largest Generation (25)

A family hierarchy is usually presented by a pedigree tree where all the nodes on the sa

迈不过友情╰/ 2022年05月30日 03:41/ 0 赞/ 80 阅读

相关 1079. Total Sales of Supply Chain (25)

A supply chain is a network of retailers（零售商）, distributors（经销商）, and suppliers（供应商）-- e

悠悠/ 2022年05月30日 02:25/ 0 赞/ 100 阅读

相关 1125. Chain the Ropes (25)

Given some segments of rope, you are supposed to chain them into one rope. Each time you

我就是我/ 2022年05月28日 12:05/ 0 赞/ 114 阅读

相关 (PAT 1125) Chain the Ropes (贪心+优先级队列的应用)

1125 Chain the Ropes （25 point(s)） Given some segments of rope, you are supposed to cha

绝地灬酷狼/ 2022年03月22日 13:14/ 0 赞/ 140 阅读

相关 poj 1125 FLoyd

题意：让你找一个点，从这个点向其它点传递信息所要的时间最短。输出这个点得编号，和最晚收到信息的人所需时间。算法： 1.Dijkstra算法一次只能求单源最短路径，而

淩亂°似流年/ 2021年11月02日 14:26/ 0 赞/ 181 阅读