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 4
46 23 26 24 10
24 is the root
26 and 23 are siblings
46 is the parent of 23
23 is a child of 10

输出样例：

F
T
F
T

思路分析：

建堆，处理命令并判断。

注意：

1.通常给一个序列建堆可以直接从n/2处倒着向下调整即可，但是本题这样会错误，因为题目给的是插入序列，往空的小根堆中依次插入，因此建堆的过程就是一个插入的过程，然后向上调整即可。

2.判断命令处理值的关系时，可以设一个pos数组保存各个数字的位置，这样就不用循环确定位置，但是有一个前提是堆中每个数字都不一样。下述题解用了循环确定的方法，时间也满足要求。

3.注意判断命题时，要小心出现越界，如给的第一个结点未叶节点，要判断第二个数是否为其子结点时，2*k 与 2*k+1就会越界。

题解：

#include <cstdio>
#include <iostream>
#include <cstring>
using namespace std;
const int MAXN = 1001;
int n, m;
int heap[MAXN];
char s1[20], s2[20], s3[20];

void upadjust(int low, int high){
	int i = high, j = i/2;
	while(j >= low){
		if(heap[i] < heap[j]){
			swap(heap[j], heap[i]);
			i = j;
			j = i/2;
		}else break;
	}
}

void create(){
	for(int i = 1; i <= n; i++){
		upadjust(1, i);
	}
}

int main(){
	scanf("%d %d", &n, &m);
	for(int i = 1; i <= n; i++) scanf("%d", &heap[i]);
	create();
	while(m--){
		int num1, num2, k;
		scanf("%d %s", &num1, &s1);
		for(int i = 1; i <= n; i++){
			if(heap[i] == num1){
				k = i;
				break;
			}
		}
		if(strcmp(s1, "is") == 0){
			scanf("%s %s", s1, s2);
			if(strcmp(s2, "root") == 0){
				if(k == 1) printf("T\n");
				else printf("F\n");
			}else{
				scanf(" %s %d", s3, &num2);
				if(strcmp(s2, "parent") == 0){
					if((2*k <= n && heap[2*k] == num2) || (2*k+1 <= n && heap[2*k+1] == num2)) printf("T\n");
					else printf("F\n");
				}else if(strcmp(s2, "child") == 0){
					if(k > 1 && heap[k/2] == num2) printf("T\n");
					else printf("F\n");
				}
			}
		}else{
			scanf("%d %s %s", &num2, &s2, &s3);
			int k2;
			if(k % 2 == 0) k2 = k+1;
			else k2 = k-1;
			if(k > 1 && k2 <= n && heap[k2] == num2) printf("T\n");
			else printf("F\n");
		}
	}
	
	return 0;
}