合并果子,浅谈堆

    xiaoxiao2021-03-26  6

    合并果子是一道经典的贪心,但是如果一味的快拍,那么: (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 这个规律很有用啊! 大家自己去理解吧!

    转载请注明原文地址: https://ju.6miu.com/read-500103.html

    最新回复(0)