思维题
合并果子（加强版）
显然，每次都找最小的两个数合并。
在合并之后查最小数，这样的操作涉及
- 添加
- 删除
- 全局最小
显然这是堆的模板。
但是发现这样的复杂度是 \(\mathcal{O(n\log n)}\) 的，不足以通过本题。所以考虑优化。
发现添加的数总是越来越大（单调不降）的，故你要考虑维护一个队列 \(q2\) 来存。
每次操作中，如果 \(q2\) 的队首 \(>\) \(q1\) 的队首，那么选择 \(q1.front\) ，反之亦然。
注意到 \(q1\) 只添不删，所以只要先排序就好了
然后维护两个队列就好了。
这时你发现了一个新的复杂度瓶颈：排序。
这样做要先让 \(q1\) 保持有序。注意到 \(\alpha\leq 10^5\) ，使用桶排序。
程式
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e7+10,alpha=1e5;
queue<int> q1,q2;
int n,x,ans;
int t[N];
inline int get(void){
int x;
if(q1.front()<q2.front() && !q1.empty() || q2.empty()) return x=q1.front(), q1.pop(), x;
else return x=q2.front(), q2.pop(), x;
}
inline int read(void){
char ch=0; int x=0;
while(!isdigit(ch)) ch=getchar();
while(isdigit(ch)) x=(x<<1)+(x<<3)+(ch^48), ch=getchar();
return x;
}
signed main(){
n=read();
for(int i=1;i<=n;++i) x=read(), ++t[x];
for(int i=1;i<=alpha;++i) if(t[i]) while(t[i]--) q1.push(i);
while(q1.size()+q2.size()!=1){
int x=get()+get();
ans+=x, q2.push(x);
}
return cout<<ans<<"\n",0;
}