当前位置：网站首页>L2-012 关于堆的判断 (25 分)（堆）

L2-012 关于堆的判断 (25 分)（堆）

2022-08-08 16:51:00 【Here_SDUT】

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

代码

#include <bits/stdc++.h>
#define LL long long
using namespace std;
const int maxn = 1e3+10;
const int inf = 0x3f3f3f3f;
const double PI = acos(-1.0);
typedef pair<int,int> PII;
int heap[maxn], n, cnt;
unordered_map<int,int> f;
void up(int x) {
    if(x >> 1 >= 1 && heap[x] < heap[x>>1]) {
        swap(heap[x],heap[x>>1]);
        up(x>>1);
    }
}

void down(int x) {
    int p = x;
    if(x << 1 | 1 <= n && heap[x<<1|1] > heap[p]) p = x<<1|1;
    if(x << 1 <= n && heap[x<<1] > heap[x]) p = x << 1;
    if(x != p) {
        swap(heap[x], heap[p]);
        down(p);
    }
}

int main(int argc, char const *argv[]) {
    int m;
    cin >> n >> m;
    for(int i = 0; i < n; i++) {
        cin >> heap[++cnt];
        up(cnt);
    }
    for(int i = 1; i <= n; i++) {
        f[heap[i]] = i;
    }
    while(m--) {
        int x, y;
        string s;
        cin >> x >>s;
        x = f[x];
        if(s == "and") {
            cin >> y >> s >>s;
            y = f[y];
            if((x >> 1) == (y >> 1)) puts("T");
            else puts("F");
        }else {
            cin >> s >> s;
            if(s == "root") {
                if(x == 1) puts("T");
                else puts("F");
            }
            else if(s == "parent") {
                cin >> s >> y;
                y = f[y];
                if((y >> 1) == x) puts("T");
                else puts("F");
            }
            else if(s == "child") {
                cin >> s >> y;
                y = f[y];
                if((x >> 1) == y) puts("T");
                else puts("F");
            }
        }
    }
    return 0;
}
原网站

版权声明
本文为[Here_SDUT]所创，转载请带上原文链接，感谢
https://cloud.tencent.com/developer/article/2068334

边栏推荐

猜你喜欢

随机推荐