PAT 1125 Chain the Ropes[一般]

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

题目大意：给出好多段绳子，每两段绳子合并在一起就长度减半，求出可能的最大的长度。

//读了好几遍，没太懂啊，那就找输入的n个数里最大的两个数呗，那折叠之后不就是最长的了吗？？？

//似乎明白了，因为组合成的绳子可以再次被折叠，所以就有一个最优解的。

//我似乎理解错题意了，是要使用全部N条绳子才可以！

#include <iostream>
#include<vector>
#include<queue>
#include<algorithm>
using namespace std;


int main(){
    int n,t;
    cin>>n;
    //是哪个头文件里的？？？
    priority_queue<int> pq;//使用优先队列存储
    for(int i=0;i<n;i++){
        cin>>t;
        pq.push(t);
    }
    int a,b,mlen=0;
    while(!pq.empty()){
        a=pq.top();pq.pop();
        b=pq.top();pq.pop();
        int m=a/2+b/2;
        if(m>mlen){
            mlen=m;
        }else break;
        pq.push(m);
    }
    cout<<mlen;
    return 0;
}

View Code

//理解错误的题意。

柳神解答：

1.不过还是复习了优先队列的头文件要包括queue。