合并果子是一道经典的贪心，但是如果一味的快拍，那么： (n-1)*log(n)*n的复杂度不卡才怪，这个时候，我们就要请出二叉树中的堆。 堆，是一棵完全二叉树，如果你想要插入或删除一个元素，并保持顺序，时间复杂度是log(n)的。所以，我们就邀请堆来解决。
#include<stdio.h> #include<stdlib.h> #include<string.h> #include<math.h> #include<iostream> #include<algorithm> using namespace std; int a[100001]; int main(){ int i,j,k,n,m; cin>>n; for(i=1;i<=n;i++){ cin>>a[i]; j=i; while(j>1){ if(a[j]<a[j/2]){ int tmp=a[j];a[j]=a[j/2];a[j/2]=tmp; j/=2; } else break; } } int ans=0; while(n>1){ // for(i=1;i<=n;i++)printf("%d%c",a[i],i==n?'\n':' '); int now=a[1]; j=1;a[1]=a[n--]; while(j*2<=n){ int ts=j; if(a[j]>a[j*2] && a[j*2]<=a[j*2+1]){ int tmp=a[j];a[j]=a[j*2];a[j*2]=tmp;j=j*2; } else if(a[j]>a[j*2+1] && a[j*2]>a[j*2+1]){ int tmp=a[j];a[j]=a[j*2+1];a[j*2+1]=tmp;j=j*2+1; } if(j>=n || j==ts)break; } now+=a[1]; j=1;a[1]=a[n--]; while(j*2<=n){ int ts=j; if(a[j]>a[j*2] && a[j*2]<=a[j*2+1]){ int tmp=a[j];a[j]=a[j*2];a[j*2]=tmp;j=2*j; } else if(a[j]>a[j*2+1] && a[j*2]>a[j*2+1]){ int tmp=a[j];a[j]=a[j*2+1];a[j*2+1]=tmp;j=j*2+1; } if(j>=n || j==ts)break; } ans+=now;a[++n]=now; // printf("%d\n",now); } cout<<ans<<endl; }我们把a数组想象成一棵完全二叉树，按顺次编码，son=father*2 or father*2+1 这个规律很有用啊！ 大家自己去理解吧！
