L2-012 关于堆的判断 - java

L2-012 关于堆的判断

---

时间限制
400 ms
内存限制
64 MB

---

题目描述：

将一系列给定数字顺序插入一个初始为空的小顶堆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

---

给定n个数 让你将这个序列弄成小根堆

再给m条语句 判断是否正确 正确输出"T", 错误输出"F"

x是根节点 代表 x是小根堆中的顶部 也就是最小的
x和y是兄弟节点 代表 x和y的父节点是同一个
x是y的父结点 代表 y的父节点是x 也就是x在y的上面一层
x是y的一个子结点 代表 x的父节点是y 也就是y在x的上面一层

---

emmmmmmm

先将序列排成小根堆 然后在统计每个数在小根堆中的位置

然后去判断每句话是否成立

x和y是兄弟节点 也就是 x的位置 / 2 = y的位置 / 2
x是y的父节点 也就是 y的位置 / 2 = x的位置

---

import java.io.*;
import java.math.*;
import java.util.*;

public class Main
{
	static int N = (int) 1e3;
//	存储小根堆
	static int tree[] = new int[N + 10];

//	交换小根堆中的两个数
	static void swap(int a, int b)
	{
		int c = tree[a];
		tree[a] = tree[b];
		tree[b] = c;
	}

//	往上走
	static void up(int u)
	{
//		当前节点不为根节点 并且 当前节点的数小于父节点的数
		while ((u >> 1) > 0 && tree[u >> 1] > tree[u])
		{
			swap(u >> 1, u);
			u >>= 1;
		}
	}

	public static void main(String[] args)
	{
		int n = sc.nextInt(), m = sc.nextInt();
		for (int i = 1; i <= n; i++)
		{
			tree[i] = sc.nextInt();
//			往上走
			up(i);
		}

//		存储每个数所在小根堆中的位置
		TreeMap<Integer, Integer> len = new TreeMap<Integer, Integer>();
		for (int i = 1; i <= n; i++)
			len.put(tree[i], i);

		while (m-- > 0)
		{
			int a = sc.nextInt();
			String s = sc.next();
			if (s.equals("is"))
			{
				s = sc.next();
//				子节点
				if (s.equals("a"))
				{
					sc.next();
					sc.next();
					int b = sc.nextInt();

					if (len.get(a) / 2 == len.get(b))
						out.println("T");
					else
						out.println("F");
				} else if (s.equals("the"))
				{
					s = sc.next();
//					根节点
					if (s.equals("root"))
					{
						if (a == tree[1])
							out.println("T");
						else
							out.println("F");
					}
//					父节点
					else if (s.equals("parent"))
					{
						sc.next();
						int b = sc.nextInt();

						if (len.get(b) / 2 == len.get(a))
							out.println("T");
						else
							out.println("F");
					}
				}
			}
//			兄弟节点
			else if (s.equals("and"))
			{
				int b = sc.nextInt();
				s = sc.next();
				s = sc.next();

				if (len.get(a) / 2 == len.get(b) / 2)
					out.println("T");
				else
					out.println("F");
			}
		}

		out.flush();
		out.close();
	}

	static Scanner sc = new Scanner(System.in);
	static PrintWriter out = new PrintWriter(System.out);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107

---

大根堆 小根堆
二叉堆
小根堆

---

如果有说错的 或者 不懂的 尽管提 嘻嘻

一起进步！！！

---

闪现