原题
将一系列给定数字顺序插入一个初始为空的小顶堆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
捷径
这道题看起来复杂,难道要我们实现一个最小堆吗?毕竟是PAT,选择合适的语言尤为重要,不知大家是否还记得Java优先队列PriorityQueue
?好像C++也有,不过不知道可不可以把优先队列维护的数组拿出来用。
其实优先队列就是一个堆,当我们不指定Comparator时默认为最小堆,通过传入自定义的Comparator函数可以实现大顶堆。
PriorityQueue<Integer> minHeap = new PriorityQueue<Integer>(); //小顶堆,默认容量为11
PriorityQueue<Integer> maxHeap = new PriorityQueue<Integer>(11,
new Comparator<Integer>(){ //大顶堆,容量11
@Override
public int compare(Integer i1,Integer i2){
return i2-i1;
}
}
);
思路
- 通过把所有数据加入到优先队列
- 把优先队列维护的数组拿出来
- 根据该关系:设父亲坐标为fatherIndex,儿子坐标为sonIndex,满足
(sonIndex-1)/2=fatherIndex
(除法向下去整数),依次判断两个节点是否是兄弟节点、父子节点和子父节点 - 如果判断是不是根节点,那么就判断它是不是数组中的第一个元素
- 如果判断兄弟节点,那么就判断两个节点的父亲是不是同一个
- 如果判断是不是父子节点,那么就根据第三点的公式代入即可
import java.util.*;
/**
* @author 太白
*/
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int n, m;
n = in.nextInt();
m = in.nextInt();
// 由于题目要求是小顶堆,所以我们不需要指定Comparator,默认是小顶堆
PriorityQueue<Integer> queue = new PriorityQueue<>();
for (int i = 0; i < n; ++i) {
queue.add(in.nextInt());
}
// 转换成Objeck数组
Object[] objeckArr= queue.toArray();
// 再转换成int数组
int[] arr = new int[n];
for(int i=0;i<n;++i) {
arr[i] = (int) objeckArr[i];
}
in.nextLine();
String str;
for (int i = 0; i < m; ++i) {
str = in.nextLine();
//System.out.println(str);
String[] strs = str.split(" ");
//System.out.println(Arrays.toString(strs));
if (strs[3].equals("root")) {
// 第一种情况
int num = Integer.parseInt(strs[0]);
if (num == arr[0]) {
yes();
} else {
no();
}
} else if (strs[1].equals("and")) {
// 第二种情况
int num1 = Integer.parseInt(strs[0]);
int num2 = Integer.parseInt(strs[2]);
int num1_index = find(arr, num1);
int num2_index = find(arr, num2);
if (getFatherIndex(num1_index) == getFatherIndex(num2_index)) {
yes();
} else {
no();
}
} else if (strs[2].equals("the")) {
int num1 = Integer.parseInt(strs[0]);
int num2 = Integer.parseInt(strs[5]);
int num1_index = find(arr, num1);
int num2_index = find(arr, num2);
if (getFatherIndex(num2_index) == num1_index) {
yes();
} else {
no();
}
} else {
int num1 = Integer.parseInt(strs[0]);
int num2 = Integer.parseInt(strs[5]);
int num1_index = find(arr, num1);
int num2_index = find(arr, num2);
if (getFatherIndex(num1_index) == num2_index) {
yes();
} else {
no();
}
}
}
}
// 找到某个值在数组中的坐标
private static int find(int[] arr, int val) {
for (int i = 0; i < arr.length; i++) {
if (arr[i] == val) return i;
}
return -1;
}
private static void yes() {
System.out.println("T");
}
private static void no() {
System.out.println("F");
}
private static int getFatherIndex(int sonIndex) {
return (sonIndex - 1) / 2;
}
}