题意

在一个果园里有 n 个果子，每个果子都有一个大小 ai​，每次选择两个果子合并，合并所需的力气为两个果子的大小之和，现在要求合并所有果子所需花费的最小力气。

思路

首先考虑合并的顺序，我们一定是每次合并当前最小的两个果子是最优的。证明：我们发现我们可以将合并的过程抽象成一颗二叉树，两个兄弟节点就代表这两个节点合并了。我们发现，每个叶子节点的贡献等于 ai​×hi​，hi​ 就是这个叶子节点的深度。不难发现将最小的节点放在最深处最优。而最深的节点就是在从下往上合并时最先合并的节点，也就是说你每次将最小的两个节点最先合并其实就等于将他们放到了二叉树的最深处。

考虑如何快速找到最小的两个果子，由于此时的 n 非常大，每次都重新排序必定是会超时的。于是我们考虑其他的方法。对于原本我们已经排好序的原序列，从中取走最小的一到两个对于后面的顺序是没有影响的，于是我们可以将新合并出来的果子分开来考虑。由于每次合并的两个果子都是最小的，所以我们合并出来的果子的大小肯定是越来越大的，于是我们可以拿一个队列来存储后面新合并出来的果子，这个队列一定是单调不降的。每次寻找最小的值也只需要在这个队列以及原有的果子中找即可。

代码

由于普通排序复杂度爆炸，又由于 ai​ 的值不大，于是可以桶排实现。

#include<bits/stdc++.h>
#define int long long
using namespace std;
queue<int>a;
queue<int>b;
int ans,n,c[100005];
inline int read(){//快读，不加会超时
	int x=0;
	char ch=getchar();
	while(ch<'0'||ch>'9'){
		ch=getchar();
	}
	while(ch>='0'&&ch<='9'){
		x*=10;
		x+=ch-'0';
		ch=getchar();
	}
	return x;
}
signed main(){
	n=read();
	for(int i=1;i<=n;i++){//桶排
		c[read()]++;
	}
	for(int i=1;i<=100000;i++){//将排好序的原序列存入一个队列当中。
		while(c[i]--){
			a.push(i);
		}
    }
	for(int i=1;i<n;i++){
		int w=0;
		for(int j=1;j<=2;j++){
			if(a.size()&&b.size()){
				if(a.front()<b.front()){
					w+=a.front();
					a.pop();
				}
				else{
					w+=b.front();
					b.pop();
				}
			}
			else if(a.size()){
				w+=a.front();
				a.pop();
			}
			else{
				w+=b.front();
				b.pop();
			}
		}
		b.push(w);
		ans+=w;
	}
	printf("%lld",ans);
	return 0;
}