显然每次选取两堆重量最小的最好。

主要要介绍的不是这个解法，而是几个奇奇怪怪的东西。

  • Heap

STL中常用的堆是priority_queue（优先队列），但是STL同样支持一个奇怪的东西为heap

heap有几个函数：make_heap，pop_heap，push_heap

具体用法右转百度。

  • 向堆中压相反数

不管是priority_queue还是heap都默认大根堆，可以取的相反数压入堆，这样就不用写奇奇怪怪的比较器了。

#include<bits/stdc++.h>
using namespace std;
int fruit[30005],ans,a,b;
int main()
{
    int n;
    cin>>n;
    for(int i=0;i<n;i++)
    {
        cin>>fruit[i];
        fruit[i]=-fruit[i];
    }
    make_heap(fruit,fruit+n);
    for(int i=n;i>1;i--)
    {
        pop_heap(fruit,fruit+i);
        pop_heap(fruit,fruit+i-1);
        fruit[i-2]+=fruit[i-1];
        ans+=fruit[i-2];
        push_heap(fruit,fruit+i-1);
    }
    cout<<-ans<<endl;
    return 0;
}