题解
每次从所有果子堆中选重量最小的两堆并累加,观察到只需要找出 最小 因此考虑用堆
代码
#include<bits/stdc++.h>
using namespace std;
int pile[10005]={0};
int len=0;
void in(int x)
{
pile[++len]=x;
int now=len;
while(pile[now]<pile[now/2]&&now>1)
{
swap(pile[now],pile[now/2]);
now/=2;
}
}
int out()
{
swap(pile[len--],pile[1]);
int son=2;
while(son<=len)
{
if(son+1<=len&&pile[son+1]<pile[son])
{
son+=1;
}
if(pile[son]<pile[son/2]) swap(pile[son],pile[son/2]);
else break;
son*=2;
}
return pile[len+1];
}
int main()
{
int n;
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
int x;
scanf("%d",&x);
in(x);
}
int ans=0;
while(len>1)
{
int sum=out()+out();
ans+=sum;
in(sum);
}
printf("%d",ans);
return 0;
}