L2-012. 关于堆的判断（最小堆）

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

分析：

1、边插入边调整。

2、写法问题，注意插入负数的符号处理。

3、堆是完全二叉树，先插入到最后，再向上调整。

#include<bits/stdc++.h>

using namespace std;

const int MAXN = 1000 + 10;

vector<string> v;

map<int, int> mp;

int a[MAXN];

int change(string s){

    int st = 0;

    if(s[0] == '-') ++st;

    int sum = 0;

    for(int i = st; i < s.size(); ++i){

        sum = sum * 10 + s[i] - '0';

    }

    if(st == 1) return -sum;

    return sum;

}

int main(){

    int N, M;

    scanf("%d%d", &N, &M);

    int cnt = 0;

    while(N--){

        ++cnt;

        scanf("%d", &a[cnt]);

        int tmp = cnt;

        while(tmp != 1){

            if(a[tmp] < a[tmp / 2]){

                swap(a[tmp], a[tmp / 2]);

                tmp /= 2;

            }

            else break;

        }

    }

    for(int i = 1; i <= cnt; ++i){

        mp[a[i]] = i;

    }

    getchar();

    string s;

    while(M--){

        v.clear();

        getline(cin, s);

        stringstream ss(s);

        string x;

        int id;

        while(ss >> x){

            v.push_back(x);

            if(x == "root") id = 1;

            else if(x == "siblings") id = 2;

            else if(x == "parent") id = 3;

            else if(x == "child") id = 4;

        }

        int sum1 = change(v[0]);

        if(id == 1){

            if(a[1] == sum1) printf("T\n");

            else printf("F\n");

        }

        else if(id == 2){

            int sum2 = change(v[2]);

            if(mp[sum1] / 2 == mp[sum2] / 2) printf("T\n");

            else printf("F\n");

        }

        else if(id == 3){

            int sum2 = change(v[5]);

            if(mp[sum2] / 2 == mp[sum1]) printf("T\n");

            else printf("F\n");

        }

        else{

            int sum2 = change(v[5]);

            if(mp[sum1] / 2 == mp[sum2]) printf("T\n");

            else printf("F\n");

        }

    }

    return 0;

}

巴特西

L2-012. 关于堆的判断（最小堆）

最新文章

热门文章