AcWing 148. 合并果子 两种做法
原题链接
简单
作者:
辉小歌
,
2021-05-20 16:32:41
,
所有人可见
,
阅读 369
小根堆做法
#include<cstdio>
#include<iostream>
#include<queue>
using namespace std;
int main(void)
{
priority_queue<int, vector<int>, greater<int> >heap;
int n; cin>>n;
while(n--)
{
int x; cin>>x;
heap.push(x);
}
long long int res=0;
while(heap.size()>1)
{
int a=heap.top(); heap.pop();
int b=heap.top(); heap.pop();
res+=a+b;
heap.push(a+b);
}
cout<<res<<endl;
return 0;
}
大根堆做法
#include<cstdio>
#include<queue>
#include<iostream>
using namespace std;
int main(void)
{
int n; cin>>n;
priority_queue<int> heap;
while(n--)
{
int x; cin>>x;
heap.push(-x);
}
long long int res=0;
while(heap.size()>1)
{
int a=heap.top(); heap.pop();
int b=heap.top(); heap.pop();
res+=(-a-b);
heap.push(-(-a-b));
}
cout<<res<<endl;
return 0;
}