题目描述

题目描述

样例

输入样例：

3 

1 2 9

输出样例

15

算法1

二叉堆

贪心

思路

我们知道，要使体力值最小，我们每次合并都得选最小的两个

于是我们就会想到用 sort排序

时间复杂度就是 n(nlogn) ，但是 n 最大为 10000 ，明显会超时

所以要用二叉堆来排序

由于优先队列默认是大根堆（队头大，队尾小），只能取最大值，所以我们要重载“<”，就可以本来越大的数越“小”，实现小根堆

C++ 代码

#include<iostream> 
#include<cstdio>
#include<vector>
#include<queue>
using namespace std;
struct node{
    int t;
};
priority_queue <node> q;
bool operator <(const node &x,const node &y)
{
    return x.t>y.t;
/*重载小于号 ,优先队列默认是大根堆，只能取到最大值，
现在想取到最小值，所以需要把优先队列改为小根堆，需要重载小于号*/
}
node a[10100];
int main()
{
    int n,ans=0;
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a[i].t);
        q.push(a[i]);
    }
    if(n==1)//特殊情况
    {
        printf("%d",a[1].t);
        return 0;
    }
    while(true)//合并果子ing 
    {
        node x,y;
        x=q.top();
        q.pop();
        y=q.top();
        q.pop();
        ans=ans+x.t+y.t;//统计体力值 
        if(q.empty())//如果队列为空
        {
            break;//合并完了，走人 
        } 
        else
        {
            node z;
            z.t=x.t+y.t;
            q.push(z);//得到这次合并果子的体力值 
        }
    }
    printf("%d",ans);
    return 0;
}