明不断取最小的两堆合并成较大的一堆是最优的。
（不太好证哦）
①**最优方案可以表示成一个二叉树。**总代价 \sum_{i=1}^{n} a_i × depth_i∑i=1nai×depthi。其中 depthdepth 是深度，也就是这堆果子在整个过程中被有效合并了几次。
注意：a_iai 都是叶子结点。非叶子结点都是合并后的产物。
②最小的两堆一定在最优方案树的最深层。
这个用反证法。假设有一个最优方案树，其最深层中没有最小的两堆。那么把最小的堆与最深层的某堆互换位置形成新方案，保证新方案存在而且新方案的代价小于原方案。
注意：最深层总是一组（一组有两个）或多组叶子节点，来表示它们被直接合并。
③同层叶子节点互换，对总代价无影响。
根据①的 \sum∑ 得。可见，最小的两堆，如果在最优方案树最深层中不是即将合并的一组，那么可以无偿换为一组。
④根据上两步，我们已经明确：最优方案需要直接合并当前最小的两堆。现在我们就进行这个操作。事实是：现在只剩 n-1n−1 堆了。我们只知道刚才进行了一个绝对不错的操作，而不记得操作之前是什么样的。我们只想对现在剩下的几堆陌生的果子进行最好的操作。忽略之前的树，于是回到①了。
#include<bits/stdc++.h>
using namespace std;
int n,a[99999],i,j,ans,ll,bj;
void put(int n){
if(a[n]<a[n/2]){
int zz=a[n];
a[n]=a[n/2];
a[n/2]=zz;
put(n/2);
}
if(n==1){
return;
}
}
void sc(int n,int l){
if(a[n]>a[n*2]&&a[n*2]<=a[n*2+1]&&n*2<=l){
int zz=a[n];
a[n]=a[n*2];
a[n*2]=zz;
sc(n*2,l);
}
else if(a[n]>a[n*2+1]&&a[n*2]>=a[n*2+1]&&n*2+1<=l){
int zz=a[n];
a[n]=a[n*2+1];
a[n*2+1]=zz;
sc(n*2+1,l);
}
else if(a[n]>a[n*2]&&n*2+1>l&&n*2<=l){
int zz=a[n];
a[n]=a[n*2];
a[n*2]=zz;
sc(n*2,l);
}
}
void get(int nn){
bj=a[1];
a[1]=a[nn+1];
sc(1,nn);
bj=a[1]+bj;
a[1]=bj;
ans=ans+bj;
sc(1,nn);
}
int main(){
cin>>n;
ll=n;
for(i=1;i<=n;i++){
cin>>a[i];
put(i);
}
for(i=1;i<n-1;i++){
ll--;
get(ll);
}
cout<<a[1]+a[2]+ans;
}