原题链接:[NOIP2004 提高组] 合并果子 / [USACO06NOV] Fence Repair G - 洛谷
目录
1. 题目描述
2. 思路分析
优先队列。
当堆数大于1时,每次将最小的两个(最小堆的堆顶)取出,并且相加,并且将它们的和重新压入最小堆。开一个变量ans,不断累加这两个最小值的和。
3. 代码实现
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
signed main(){
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
int n; cin>>n;
priority_queue<int,vector<int>,greater<int>> pq;
for(int i=1;i<=n;i++){
int x; cin>>x;
pq.push(x);
}
int ans=0;
while(pq.size()>1){
int x=pq.top(); pq.pop();
int y=pq.top(); pq.pop();
ans+=x+y;
pq.push(x+y);
}
cout<<ans<<endl;
return 0;
}