当前位置:首页 » 《关注互联网》 » 正文

PAT(甲级)2021年春季考试 7-3 Structure of Max-Heap (25 分) 最大堆_球王武磊的博客

9 人参与  2021年09月08日 07:23  分类 : 《关注互联网》  评论

点击全文阅读


PAT(甲级)2021年春季考试
7-3 Structure of Max-Heap (25 分) 最大堆

【题目描述】
In computer science, a max-heap is a specialized tree-based data structure that satisfies the heap property: if P is a parent node of C, then the key (the value) of P is greater than or equal to the key of C. A common implementation of a heap is the binary heap, in which the tree is a complete binary tree.

Your job is to first insert a given sequence of integers into an initially empty max-heap, then to judge if a given description of the resulting heap structure is correct or not. There are 5 different kinds of description statements:

x is the root
x and y are siblings
x is the parent of y
x is the left child of y
x is the right child of y

Input Specification:
Each input file contains one test case. For each case, the first line gives 2 positive integers: N (≤1,000), the number of keys to be inserted, and M (≤20), the number of statements to be judged. Then the next line contains N distinct integer keys in [−10 4,10 4] which are supposed to be inserted into an initially empty max-heap. Finally there are M lines of statements, each occupies a line.

Output Specification:
For each statement, print 1 if it is true, or 0 if not. All the answers must be print in one line, without any space.

Sample Input:

5 6
23 46 26 35 88
35 is the root
46 and 26 are siblings
88 is the parent of 46
35 is the left child of 26
35 is the right child of 46
-1 is the root

Sample Output:

011010

【解题思路】

按照输入,将数字逐个加入最大堆中,并对堆进行调整。完成建堆以后,用一个map存储各数字在堆中的位置(数组下标),以供后面查询。

下面输入每行字符串,这里处理比较巧妙,逐个单词输入,并不需要用到复杂的字符串处理。具体看代码实现,每部分加上了注释,代表是五种查询中的哪一种,然后通过map找到数字对应的数组下标,判断是否符合,输出结果即可。

【满分代码】

#include <iostream>
#include <cstdio>
#include <string>
#include <map>
#include <algorithm>
using namespace std;
int main()
{
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0); 
	int n,m,a,b,d[1005];
	string x,y,z,s,t;
	cin>>n>>m;
	for(int i=1;i<=n;i++)
	{
		cin>>d[i];
		for(int j=i;j>1;j/=2)
		{
			if(d[j]>d[j/2])
				swap(d[j],d[j/2]);
			else
				break;
		}
	}//建最大堆 
	map<int,int> pos;
	for(int i=1;i<=n;i++)
		pos[d[i]]=i;//记录各数字在堆中的位置 
	while(m--)
	{
		cin>>a>>x;
		if(x=="and")//a和b是否为兄弟结点 
		{
			cin>>b>>y>>z;
			if(pos[a]==0||pos[b]==0||pos[a]==pos[b])//结点a或b不存在,或者a和b是同一个结点 
			{
				cout<<"0";
				continue;
			}
			if(pos[a]/2==pos[b]/2)
				cout<<"1";
			else
				cout<<"0";
		}
		else//(x=="is") 
		{
			cin>>y>>z;
			if(z=="root")//a是否为根节点 
			{
				if(pos[a]==1)
					cout<<"1";
				else
					cout<<"0";
			}
			else if(z=="parent")//a是否为b的父亲结点 
			{
				cin>>s>>b;
				if(pos[a]==0||pos[b]==0)
				{
					cout<<"0";
					continue;
				}
				if(pos[a]==pos[b]/2)
					cout<<"1";
				else
					cout<<"0";
			}
			else if(z=="left")//a是否为b的左子结点 
			{
				cin>>s>>t>>b;
				if(pos[a]==0||pos[b]==0)
				{
					cout<<"0";
					continue;
				}
				if(pos[a]==pos[b]*2)
					cout<<"1";
				else
					cout<<"0";
			}
			else if(z=="right")//a是否为b的右子结点 
			{
				cin>>s>>t>>b;
				if(pos[a]==0||pos[b]==0)
				{
					cout<<"0";
					continue;
				}
				if(pos[a]==pos[b]*2+1)
					cout<<"1";
				else
					cout<<"0";
			}
		}
	}
	return 0;
}

点击全文阅读


本文链接:http://m.zhangshiyu.com/post/27311.html

结点  数字  下标  
<< 上一篇 下一篇 >>

  • 评论(0)
  • 赞助本站

◎欢迎参与讨论,请在这里发表您的看法、交流您的观点。

最新文章

  • 山海不相逢内容精选(温逸尘沈衿)_山海不相逢内容精选(温逸尘沈衿)
  • (番外)+(全书)霍沉洲沈青禾此去经年人未还(霍沉洲沈青禾)_(霍沉洲沈青禾此去经年人未还)列表_笔趣阁(霍沉洲沈青禾)
  • (番外)+(全书)霍沉洲沈青禾(此去经年人未还霍沉洲沈青禾)完结_(霍沉洲沈青禾)列表_笔趣阁(此去经年人未还霍沉洲沈青禾)
  • 「重回八零,拒绝替嫁冲喜」章节彩蛋限时释出‌_卫东玉兰苏夏人气小说未删减节选
  • 重生七零祁同伟不再是农民儿子结局+番外纯净版全书免费重生七零祁同伟不再是农民儿子结局+番外纯净版全书免费
  • 傅雅宁的神女老婆,却在背地承欢作乐顾尘傅雅宁全书在线
  • 全文神女老婆,却在背地承欢作乐全局(顾尘傅雅宁)列表_全文神女老婆,却在背地承欢作乐全局
  • (番外)+(全书)此去经年人未还全书+番外+后续免费下载_(沈青禾霍沉洲)此去经年人未还全书+番外+后续列表_笔趣阁(沈青禾霍沉洲)
  • 完结文毁容的姐姐和瞎眼的我离开后,姜家两兄弟悔哭了+后续列表_完结文毁容的姐姐和瞎眼的我离开后,姜家两兄弟悔哭了+后续(林梦婉)
  • 妻子辱我爸受贿自杀,我掏出一等军功章节选推荐_[陈素云辰朋友]小说精彩章节分享
  • 全书浏览苔藓爬满旧日诺言新上(顾砚廷慕晚夏)_苔藓爬满旧日诺言新上(顾砚廷慕晚夏)全书结局
  • 顾尘傅雅宁(神女老婆,却在背地承欢作乐+后续+结局)结局_(顾尘傅雅宁神女老婆,却在背地承欢作乐+后续+结局全书结局)结局列表_笔趣阁(顾尘傅雅宁)

    关于我们 | 我要投稿 | 免责申明

    Copyright © 2020-2022 ZhangShiYu.com Rights Reserved.豫ICP备2022013469号-1