题目链接:点击打开链接
题目大意:略。
解题思路:此题为边插入边建堆,而不是先按层序遍历建好树再调整成堆;注意兄弟结点的判断条件(小偶大奇且(奇 - 偶==1))。
AC 代码
usingnamespacestd; typedeflonglongll; intn, res, a[1009]; voidfind_heap(intrt, intd) { if(rt>n||rt<=0) return; if(a[rt]==d){res=rt; return;} if(a[rt]<d) find_heap(rt*2,d); if(a[rt]<d) find_heap(rt*2+1,d); } intmain() { intm,n1,n2,rt; scanf("%d%d",&n,&m); for(inti=1;i<=n;i++) { scanf("%d",&a[i]); make_heap(a+1,a+1+i,greater<int>()); } rt=a[1]; getchar(); strings; while(m--) { getline(cin,s); intf=0, id1, id2; if(sscanf(s.c_str(),"%d and %d are siblings",&n1,&n2)==2) { res=0; find_heap(1,n1); id1=res; res=0; find_heap(1,n2); id2=res; if(id1>id2) swap(id1,id2); if(id1%2==0&&id2%2==1&&id2-id1==1) f=1; } elseif(sscanf(s.c_str(),"%d is the parent of %d",&n1,&n2)==2) { res=0; find_heap(1,n1); id1=res; res=0; find_heap(1,n2); id2=res; if(id1*2==id2||id1*2+1==id2) f=1; } elseif(sscanf(s.c_str(),"%d is a child of %d",&n1,&n2)==2) { res=0; find_heap(1,n1); id1=res; res=0; find_heap(1,n2); id2=res; if(id2*2==id1||id2*2+1==id1) f=1; } elseif(sscanf(s.c_str(),"%d is the root",&n1)==1) { if(n1==rt) f=1; } puts(f?"T":"F"); } return0; }