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”。

输入样例：

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


思路：不想自己写堆所以用了STL中heap,然后剩下的就比较暴力了，未满十八岁请在监护人的陪同下观看。

#include<string>

#include<vector>

#include<sstream>

#include<iostream>

#include<functional>

#include<algorithm>

using namespace std;

int main()

{

    int n, m; cin >> n >> m;

    vector<int>vec;

    for (int i = ; i < n; i++){

        int num; cin >> num;

        vec.push_back(num);

        push_heap(vec.begin(), vec.end(), greater<int>());

    }

    getchar();

    while (m--){

        bool flag = false;

        string temp;

        stringstream ss;

        ss.clear();

        getline(cin, temp);

        ss << temp;

        if (temp.find("root") < temp.size()){

            int cnt; ss >> cnt;

            if (vec[] == cnt)flag = true;

        }

        else if (temp.find("siblings") < temp.size()){

            int a, b; string c;

            ss >> a >> c >> b;

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

                if (vec[i] == a){

                    int bro = i %  ==  ? i +  : i - ;

                    if (vec[bro] == b)flag = true;

                    break;

                }

                if (vec[i] == b){

                    int bro = i %  ==  ? i +  : i - ;

                    if (vec[bro] == a)flag = true;

                    break;

                }

            }

        }

        else if (temp.find("parent") < temp.size()){

            int er, ba; string a, b, c, d;

            ss >> ba >> a >> b >> c >> d >> er;

            for (int i = ; i < vec.size(); i++)

            if (vec[i] == ba){

                if ( * i +  < vec.size() && vec[ * i + ] == er){

                    flag = true; break;

                }

                if ( * i +  < vec.size() && vec[ * i + ] == er){

                    flag = true; break;

                }

            }

        }

        else if (temp.find("child") < temp.size()){

            int er, ba; string a, b, c, d;

            ss >> er >> a >> b >> c >> d >> ba;

            for (int i = ; i < vec.size(); i++)

            if (vec[i] == ba){

                if ( * i +  < vec.size() && vec[ * i + ] == er){

                    flag = true; break;

                }

                if ( * i +  < vec.size() && vec[ * i + ] == er){

                    flag = true; break;

                }

            }

        }

        if (flag)cout << "T" << endl;

        else cout << "F" << endl;

    }

    return ;

}

巴特西

L2-012. 关于堆的判断（STL中heap）

L2-012. 关于堆的判断

最新文章

热门文章