1070 结绳 (25分)

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

rope.jpg

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

输入格式:

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

输出格式:

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

输入样例:

8
10 15 12 3 4 13 1 15
			

输出样例:

14
			
思路:贪心算法,哈夫曼树的原理,分析:假设 12 14 16 18,如果从最大的18和16开始,结成的绳子为9+8=17;,然后是8.5+7=15.5;然后是7.75+6=13.75;越结越小,越往下界靠近;如果是从最小的12和14开始,6+7=13;6.5+8=14.5;7.25+9=16.25,越来越往上界靠近,所以总结:先每次取最小的两个结绳,结好后的长度放入,接着取最小的两个直到最后,这里利用小根堆来存储数据,priority_queue<double,vector<double>,greater<double> >q;
小二上代码:
#include<iostream>
#include<cstdio>
#include<queue>
using namespace std;
priority_queue<double,vector<double>,greater<double> >q;//建立小根堆保存数据
int main()
{
    int n;
    while(cin>>n)
    {
        while(q.empty()==false)q.pop();//清空堆
        int x;
        for(int i=0;i<n;i++)//入堆
        {
           scanf("%d",&x);
            q.push(x);
        }
        while(q.size()>1)//当堆里只剩一个时退出循环
        {
            double a=q.top();//取最小的
            q.pop();//出堆
            double b=q.top();//再取最小的
            q.pop();//出堆
            q.push(a/2+b/2);//新绳入堆
        }
        //cout<<(int)q.top()<<endl;
       printf("%d\n",(int)q.top());//因为要向下取整,所以强制类型转化成int形就向下取整了
    }
    return 0;
}