题目解析
给定n个数 让你将这个序列弄成小根堆
再给m条语句 判断是否正确 正确输出T, 错误输出F
- x是根节点
- 代表 x是小根堆中的顶部 也就是最小的
- x和y是兄弟节点
- 代表 x和y的父节点是同一个
- x是y的父结点
- 代表 y的父节点是x 也就是x在y的上面一层
- x是y的一个子结点
- 代表 x的父节点是y 也就是y在x的上面一层
解题思路
先将序列排成小根堆 然后在统计每个数在小根堆中的位置
然后去判断每句话是否成立
x和y是兄弟节点 也就是
x是y的父节点 也就是
代码
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);
}