P1090 合并果子
本题要用到堆
一个小根堆
每次取出两堆,合并成一堆,为了让多多花费体力最少,我们要尽量少的重复大堆的合并,因此每次合并完以后,要把新的一坨放到堆里排一排,维护一个堆
有必要强调一下这个合并的操作:
(1)取出最小的一个(或一坨)果子 x
(2)再取出最小的一个(或一坨)果子 y
(3)合并为一坨 x+y
(4)体力值自然要加上 x+y 了
(5)把 x+y 放到堆里维护一下这个堆,保证下次从堆中取出小的一个或一坨
【代码】:
#include<bits/stdc++.h> using namespace std; int n,guo,heap_size,ans=,ans1=,x,y;
int heap[]; void put(int d) //小根堆入堆
{
int now,next;
heap[++heap_size]=d;
now=heap_size;
while(now>)
{
next=now>>;
if(heap[now]>=heap[next]) break;
else swap(heap[now],heap[next]);
now=next;
}
}
int get() //小根堆出堆
{
int now,next,res;
res=heap[];
heap[]=heap[heap_size--];
now=;
while(now*<=heap_size)
{
next=now*;
if(next<heap_size&&heap[next+]<heap[next]) next++;
if(heap[now]>heap[next])
swap(heap[now],heap[next]);
now=next;
}
return res;
} int main()
{
scanf("%d",&n);
for(int i=;i<=n;i++)
{
scanf("%d",&guo);
put(guo);
} for(int i=;i<n ;i++) //每次把两堆果子合为一堆,一共需要合并n-1次
{
x=get(); //取出一堆小果子
y=get(); //再取出一堆小果子
ans+=x+y; //体力等于搬运这两个之和
put(x+y); //把这两个放进堆
} cout<<ans; return ;
}