PAT L2-012. 关于堆的判断(最小堆调整)

本文链接：https://blog.csdn.net/zero_witty/article/details/51706046

题目链接：https://www.patest.cn/contests/gplt/L2-012

L2-012. 关于堆的判断

时间限制

400 ms

内存限制

65536 kB

代码长度限制

8000 B

判题程序

Standard

作者

陈越

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

题意and解题思路:让你建立一个最小堆，根据这个最小堆的实际情况去判断下列命题是否正确（有个坑点，这个最小堆不是等所有数据输入完才开始调整的，而是没进一个元素，就进行调整的），至于最小堆调整，便是将保证父节点比子节点大，若不是其中最小的，则取左右结点中较小的一个进行交换，一直到没有交换出现，便中断此操作。

#include<cstdio>
#include<cstring>
#include<vector>
#include<iostream>
#include<queue>
#include<map>
using namespace std;
const int maxn = 3005;
int m;
int val[maxn];
int vis[maxn];
map<int,int>ma;
int f;
void adjust(int x,int n)
{
    vis[x] = 1;
    int l = 2*x;
    int r = 2*x+1;
    if(r<=n)
    {
        if(val[r]<val[l])
        {
            if(val[r]<val[x])
            {
                swap(val[r],val[x]);
                f=1;
            }
        }
        else if(val[l]<val[r])
        {
            if(val[l]<val[x])
            {
                swap(val[l],val[x]);
                f=1;
            }
        }
    }
    else if(l<=n)
    {
        if(val[l]<val[x])
        {
            swap(val[l],val[x]);
            f=1;
        }
    }
}
int main()
{

    int n;
    cin >> n >> m;
    for(int i = 1 ; i <= n ; i ++)
    {
        cin >> val[i];
        while(1)
        {
            f = 0;
            memset(vis,0,sizeof(vis));
            for(int j = i ; j >= 2; j --)
            {
                int fa = j/2;
                if(!vis[fa])
                    adjust(fa,i);
            }
            if(!f)
                break;
        }

    }

//    for(int i = 1 ; i <= n ; i ++)
//        cout << val[i] <<endl;
    for(int i = 1; i <= n ; i ++)
        ma[val[i]] = i;
    for(int i = 0 ; i < m; i ++)
    {
        int a,b ;
        scanf("%d",&a);
        int id1,id2;
        id1 = ma[a];
        string s1;
        cin >> s1;
        if(s1[0]=='a')
        {
            scanf("%d",&b);
            getline(cin,s1);
            id2 = ma[b];
            if(id1==id2)
                puts("F");
            else if((id1/2)==(id2/2))
                puts("T");
            else
                puts("F");
        }
        else
        {
            cin >> s1;
            if(s1[0]=='a')
            {
                cin >> s1;
                cin >> s1;
                scanf("%d",&b);
                id2 = ma[b];
                if(id1==id2)
                    puts("F");
                else if(id1/2==id2)
                    puts("T");
                else
                    puts("F");
            }
            else
            {
                cin >> s1;
                if(s1[0]=='r')
                {

                    if(id1==1)
                        puts("T");
                    else
                        puts("F");
                }
                else
                {
                    cin >> s1;
                    scanf("%d",&b);
                    id2 = ma[b];
//                    cout << a<<' '<<id1<<' '<<b <<' '<<id2<<' ';
                    if(id1==id2)
                        puts("F");
                    else  if(id1==(id2/2))
                        puts("T");
                    else
                        puts("F");
                }
            }
        }
    }
//     for(int i = 1 ; i <= n ; i ++)
//        cout << val[i] <<endl;
    return 0 ;
}