PAT 天梯赛 L2-012. 关于堆的判断【Heap】【STL】

题目链接

https://www.patest.cn/contests/gplt/L2-012

思路

使用 STL 里面有关 Heap 的函数

std::make_heap将[start, end)范围进行堆排序，默认使用less, 即最大元素放在第一个。

std::pop_heap将front（即第一个最大元素）移动到end的前部，同时将剩下的元素重新构造成(堆排序)一个新的heap。

std::push_heap对刚插入的（尾部）元素做堆排序。

std::sort_heap将一个堆做排序,最终成为一个有序的系列，可以看到sort_heap时，必须先是一个堆（两个特性：1、最大元素在第一个 2、添加或者删除元素以对数时间），因此必须先做一次make_heap.

make_heap, pop_heap, push_heap, sort_heap都是标准算法库里的模板函数，用于将存储在vector/deque 中的元素进行堆操作

根据题目的意思是要用 push_heap 一个一个插入

而不能用 make_heap

因为 push_heap 和 make_heap 构造的堆是不一样的

比如

3 6 2 4 1 5 这组数据

make_heap

push_heap

然后用一个 map 将元素与其数组下标对应起来要从1 开始

根节点就是判断一下其数组下标是不是 1

x 和 y 是兄弟节点

就是判断一下

a = x 的数组下标 / 2

b = y 的数组下标 / 2

a 对应的数和b 对应的数是不是相等并且 a != b

x 是 y 的父节点

就是判断一下 y 的数组下标 / 2 是不是等于 x 的数组下标

x 是

x 是 y 的子节点

就是判断一下 x 的数组下标 / 2 是不是等于 y 的数组下标

AC 代码

#include <cstdio>

#include <cstring>

#include <ctype.h>

#include <cstdlib>

#include <cmath>

#include <climits>

#include <ctime>

#include <iostream>

#include <algorithm>

#include <deque>

#include <vector>

#include <queue>

#include <string>

#include <map>

#include <stack>

#include <set>

#include <numeric>

#include <sstream>

#include <iomanip>

#include <limits>

#define CLR(a) memset(a, 0, sizeof(a))

using namespace std;

typedef long long ll;

typedef long double ld;

typedef unsigned long long ull;

typedef pair <int, int> pii;

typedef pair <ll, ll> pll;

typedef pair<string, int> psi;

typedef pair<string, string> pss;

const double PI = 3.14159265358979323846264338327;

const double E = exp(1);

const double eps = 1e-6;

const int INF = 0x3f3f3f3f;

const int maxn = 1e3 + 5;

const int MOD = 1e9 + 7;

int main()

{

    map <int, int> vis;

    int n, m, num;

    scanf("%d%d", &n, &m);

    vector <int> v;

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

    {

        scanf("%d", &num);

        num = -num;

        v.push_back(num);

        push_heap(v.begin(), v.end());

    }

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

        vis[-v[i]] = i + 1;

    while (m--)

    {

        int a, b, c, d;

        string s;

        cin >> a;

        cin >> s;

        if (s == "and")  //2

        {

            cin >> b;

            cin >> s;

            cin >> s;

            c = vis[a];

            d = vis[b];

            if (v[c / 2] == v[d / 2] && c != d)

                cout << "T\n";

            else

                cout << "F\n";

        }

        else

        {

            cin >> s;

            if (s == "the")

            {

                cin >> s;

                if (s == "root")  //1

                {

                    if (vis[a] == 1)

                        cout << "T\n";

                    else

                        cout << "F\n";

                }

                else    // 3

                {

                    cin >> s;

                    cin >> b;

                    c = vis[a];

                    d = vis[b];

                    if (d / 2 == c)

                        cout << "T\n";

                    else

                        cout << "F\n";

                }

            }

            else  //4

            {

                cin >> s;

                cin >> s;

                cin >> b;

                c = vis[a];

                d = vis[b];

                if (c / 2 == d)

                    cout << "T\n";

                else

                    cout << "F\n";

            }

        }

    }

}

巴特西

PAT 天梯赛 L2-012. 关于堆的判断【Heap】【STL】

最新文章

热门文章

巴特西

PAT 天梯赛 L2-012. 关于堆的判断 【Heap】【STL】

最新文章

热门文章

PAT 天梯赛 L2-012. 关于堆的判断【Heap】【STL】