首页 > 代码库 > L2-012. 关于堆的判断
L2-012. 关于堆的判断
L2-012. 关于堆的判断
时间限制
400 ms
内存限制
65536 kB
代码长度限制
8000 B
判题程序
Standard
作者
陈越
将一系列给定数字顺序插入一个初始为空的小顶堆H[]。随后判断一系列相关命题是否为真。命题分下列几种：
- “x is the root”：x是根结点；
- “x and y are siblings”：x和y是兄弟结点；
- “x is the parent of y”：x是y的父结点；
- “x is a child of y”：x是y的一个子结点。
输入格式：
每组测试第1行包含2个正整数N（<= 1000）和M（<= 20），分别是插入元素的个数、以及需要判断的命题数。下一行给出区间[-10000, 10000]内的N个要被插入一个初始为空的小顶堆的整数。之后M行，每行给出一个命题。题目保证命题中的结点键值都是存在的。
输出格式：
对输入的每个命题，如果其为真，则在一行中输出“T”，否则输出“F”。
输入样例：5 446 23 26 24 1024 is the root26 and 23 are siblings46 is the parent of 2323 is a child of 10输出样例：
FTFT
分析：这里是小顶堆（还有大顶堆），小顶堆的特点就是：父节点的值一定小于子节点的值。
堆有几个基本操作，添加和删除（删除默认删除最小元素）
基本代码如下
//插入操作
1 int sz=0; 2 //sz设置为一个全局变量，用来表示当前要插入的位置 3 void push(int x){ 4 int i=sz++; 5 while(i>0){ 6 int p=(i-1)/2; //找到要插入位置的父节点位置 7 if(a[p]<=x) break; 8 a[i]=a[p]; 9 i=p; //移动要插入的下标10 }11 a[i]=x;12 }
ac代码：
1 #include<bits/stdc++.h> 2 using namespace std; 3 int a[10000]; 4 int n, m, sz=0; 5 void push(int x){ 6 int i=sz++; 7 while(i>0){ 8 int p=(i-1)/2; 9 if(a[p]<=x) break;10 a[i]=a[p];11 i=p;12 }13 a[i]=x;14 }15 int main(){16 cin>>n>>m;17 for(int i=0; i<n; i++){18 int x;19 cin>>x;20 push(x);21 }22 for(int cnt=0; cnt<m; cnt++){23 //cout<<cnt<<" "<<m<<endl;24 int x, y;25 string ch, c_a, c_b, c_c;26 cin>>x;27 //cout<<x<<" ";28 cin>>ch;29 //cout<<ch<<" ";30 if(ch[0]==‘a‘){31 cin>>y;32 for(int j=0; j<n; j++){33 if(a[j]==x){34 if(j==0){35 cout<<"F"<<endl;36 break;37 }38 if(a[(j-1)/2*2+1]==y||a[(j-1)/2*2+2]==y) cout<<"T"<<endl;39 else cout<<"F"<<endl;40 }41 }42 cin>>c_a>>c_b;43 }else{44 string c;45 cin>>c;46 if(c[0]==‘a‘){47 cin>>c_a>>c_b;48 cin>>y;49 for(int j=0; j<n; j++){50 if(a[j]==y){51 if(a[j*2+1]==x||a[j*2+2]==x) cout<<"T"<<endl;52 else cout<<"F"<<endl;53 break;54 }55 }56 }else{57 string p;58 cin>>p;59 if(p[0]==‘r‘){60 if(a[0]==x) cout<<"T"<<endl;61 else cout<<"F"<<endl;62 }else{63 int z;64 cin>>c_a;65 cin>>z;66 for(int j=0; j<n; j++){67 if(a[j]==x){68 if(a[j*2+1]==z||a[j*2+2]==z) cout<<"T"<<endl;69 else cout<<"F"<<endl;70 break;71 }72 }73 }74 }75 }76 }77 return 0;78 }
L2-012. 关于堆的判断
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。