【题解】药剂合成

题意

给你瓶药剂，每瓶药剂都有个能量，每次要挑出两瓶药剂合成为一瓶药剂，合成后的药剂能量为。求最后合成只剩一瓶药剂时他能量最大可能值。

题解

由于先合成的实际上每次都会被减半，合成几次就减半几次，所以一开始合成能量小的是能让损耗降低的。所以考虑贪心，也就是哈夫曼树，使用一个优先队列用来存储。每次从队首取两个值，将其的和的二分之一压入队中，直至队的大小为1。输出即可，有一点是，答案可能不为小数，那么输出需要注意一下。

复杂度

时间复杂度O(nlogn)

代码

#include<bits/stdc++.h>
using namespace std;
priority_queue<double,vector<double>,greater<double> > q;
int main()
{
    int n;
    scanf("%d",&n);
    for(int i=0;i<n;i++)
    {
        double a;
        scanf("%lf",&a);
        q.push(a);
    }
    while(q.size()>1){
        double a=q.top();q.pop();
        double b=q.top();q.pop();
        q.push((a+b)/2);
    }
    if(fmod(q.top(),1.0)==0.0)
        printf("%.0f\n",q.top());
    else
        printf("%.1f\n",q.top());
    return 0;
}