pat乙级1070

1070 结绳 (25分)

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

给定 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;
}