AcWing 148. 合并果子
原题链接
简单
手写堆模板题
#include<iostream>
using namespace std;
const int N = 10010;
int n;
int heap[N];
void down(int x){
int t = x;
if(2*x <= n && heap[2*x] < heap[t]) t = 2*x;
if(2*x + 1 <= n && heap[2*x + 1] < heap[t]) t = 2*x + 1;
if(heap[t] < heap[x]){
swap(heap[t], heap[x]);
down(t);
}
}
void up(int x){
while(x > 1 && heap[x/2] > heap[x]){
swap(heap[x], heap[x/2]);
x >>= 1;
}
}
int main(){
cin >> n;
for(int i = 1; i <= n; i++) cin >> heap[i];
for(int i = n/2; i >= 1; i--) down(i);
int res = 0;
while(n > 1){
int a = heap[1];
heap[1] = heap[n--];
down(1);
int b = heap[1];
heap[1] = heap[n--];
down(1);
res += a + b;
heap[++n] = a + b;
up(n);
}
cout << res << endl;
}