思路
最后的状态为有 $n$ 个数,第 $i$ 个数为 $a_i$。
考虑从最后逆推回去,可以发现这很类似于求解哈夫曼树的过程。
只不过一次合并时可以是两个节点,也可以是三个节点。
每次合并三个节点,节点数减二。
如果总节点数为奇数,那么就可以一直三个节点式的合并。
否则,会有一次两个节点式的合并,显然要一开始选最小的两个点进行合并,这样对总代价的贡献最小。
代码实现
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 2e5+5;
int n;
int ans;
priority_queue<int,vector<int>,greater<int>>pq;
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
cin>>n;
for(int i=1;i<=n;i++){
int x; cin>>x;
pq.push(x);
}
if(n%2==0){
int val = 0;
val += pq.top(); pq.pop();
val += pq.top(); pq.pop();
ans += val;
pq.push(val);
}
while(pq.size()>1){
int val = 0;
for(int i=0;i<3;i++){
val += pq.top(); pq.pop();
}
ans += val;
pq.push(val);
}
cout<<ans;
}