C4top-关于堆的判断（最小堆）

妖狐艹你老母 2022-09-30 06:45 162阅读 0赞

关于堆的判断

将一系列给定数字顺序插入一个初始为空的小顶堆`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`（\\le≤ 1000）和`M`（\\le≤ 20），分别是插入元素的个数、以及需要判断的命题数。下一行给出区间\[-10000, 10000\]\[−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

*  时间限制：400ms
 *  内存限制：64MB
 *  代码长度限制：16kB
 *  判题程序：系统默认
 *  作者：陈越
 *  单位：浙江大学

#### 题目判定 ####

##### 解题思路 #####

用数组模拟一个最小堆，输入一个数就更新一次，不能输入完毕后一次性建堆。

根据每句话的特点分辨出要求的是什么，并分离出数值量。

父节点下标如果是i，则子节点下标是i\*2+1和 i\*2。

注意可能存在负数，如果用的一次读入一行含空格的字符穿，还需要吃掉第一行的回车符。

判断输入的代码巨丑……见谅(っ\*´Д\`)っ

##### 解题程序 #####

#include<cstdio>
    #include<cstring>
    #include<cmath>
    #include<set>
    #include<cstdlib>
    #include<iostream>
    #include<algorithm>
    using namespace std;
    #define MAXN 200010
    #define INF 0x3f3f3f3f
    int heap[MAXN],sz=0;
    int cmp(int a,int b)
    {
        return a>b;
    }
    void push(int x)
    {
        int i=++sz;
        while(i>1)
        {
            int p=i/2;//父亲节点的编号
            if(heap[p]<=x) break;//已经没有大小颠倒
            heap[i]=heap[p];//交换节点数值
            i=p;
        }
        heap[i]=x;
    }
    
    int pop()
    {
        int ret=heap[0];
        int temp=sz;
        int x=heap[--temp];
        int i=0;
        while(i*2+1<temp)
        {
            int a=i*2+1,b=i*2+2;
            if(b<temp&&heap[b]<heap[a]) a=b;
            if(heap[a]>=x) break;
            heap[i]=heap[a];
            i=a;
        }
        heap[i]=x;
        return ret;
    }
    int main()
    {
    #ifdef ONLINE_JUDGE
    #else
        freopen("G:/cbx/read.txt","r",stdin);
        //freopen("G:/cbx/out.txt","w",stdout);
    #endif
        ios::sync_with_stdio(false);
        cin.tie(0);
        int n,m;
        cin>>n>>m;
        for(int i=0; i<n; ++i)
        {
            int x;
            cin>>x;
            push(x);
        }
        int flag=-1;
        char s[100];
        cin.getline(s,100);// 吃掉回车符
        for(int i=0; i<m; ++i)
        {
            int a=0,b=0,pos,minu=1;
            cin.getline(s,100);
            //cout<<s<<endl;
            int len=strlen(s);
            if(s[len-1]=='t')//是根结点
            {
                flag=1;
                for(int j=0; j<len; ++j)
                {
                    if(s[j]=='-')
                    {
                        minu=-1;
                        continue;
                    }
                    a*=10;
                    a+=int(s[j]-'0');
                    if(s[j+1]==' ')
                    {
                        a*=minu;
                        break;
                    }
                }
            }
            else if(s[len-1]=='s')//是兄弟结点
            {
                flag=2;
                for(int j=0; j<len; ++j)
                {
                    if(s[j]=='-')
                    {
                        minu=-1;
                        continue;
                    }
                    a*=10;
                    a+=int(s[j]-'0');
                    if(s[j+1]==' ')
                    {
                        a*=minu;
                        minu=1;
                        pos=j+6;
                        break;
                    }
                }
                for(int j=pos; j<len; ++j)
                {
                    if(s[j]=='-')
                    {
                        minu=-1;
                        continue;
                    }
                    b*=10;
                    b+=int(s[j]-'0');
                    if(s[j+1]==' ')
                    {
                        b*=minu;
                        break;
                    }
                }
            }
            else
            {
                int cnt=0;
                for(int j=0; j<len; ++j)
                {
                    if(s[j]==' ') ++cnt;
                    if(cnt==2)
                    {
                        if(s[j+1]=='t')
                        {
                            flag=3;//是父结点
                            for(int k=0; k<len; ++k)
                            {
                                if(s[k]=='-')
                                {
                                    minu=-1;
                                    continue;
                                }
                                a*=10;
                                a+=int(s[k]-'0');
                                if(s[k+1]==' ')
                                {
                                    a*=minu;
                                    minu=1;
                                    pos=k+19;
                                    break;
                                }
                            }
                            for(int k=pos; k<len; ++k)
                            {
                                if(s[k]=='-')
                                {
                                    minu=-1;
                                    continue;
                                }
                                b*=10;
                                b+=int(s[k]-'0');
                                if(s[k+1]=='\0')
                                {
                                    b*=minu;
                                    break;
                                }
                            }
                        }
                        else if(s[j+1]=='a')
                        {
                            flag=4;//是子结点
                            for(int k=0; k<len; ++k)
                            {
                                if(s[k]=='-')
                                {
                                    minu=-1;
                                    continue;
                                }
                                a*=10;
                                a+=int(s[k]-'0');
                                if(s[k+1]==' ')
                                {
                                    a*=minu;
                                    minu=1;
                                    pos=k+16;
                                    break;
                                }
                            }
                            for(int k=pos; k<len; ++k)
                            {
                                if(s[k]=='-')
                                {
                                    minu=-1;
                                    continue;
                                }
                                b*=10;
                                b+=int(s[k]-'0');
                                if(s[k+1]=='\0')
                                {
                                    b*=minu;
                                    break;
                                }
                            }
                        }
                        if(flag!=-1) break;
                    }
                }
            }
            //cout<<a<<" "<<b<<endl;
            if(flag==1)//是根结点
            {
                if(heap[1]==a) cout<<"T"<<endl;
                else cout<<"F"<<endl;
            }
            else if(flag==2)//是兄弟结点
            {
                int j=0;
                for(int i=1; i<=n; ++i)
                    if(heap[i]==a)
                    {
                        j=i;
                        break;
                    }
                j/=2;
                if(j!=0&&((heap[j*2]==a&&heap[j*2+1]==b)||(heap[j*2]==b&&heap[j*2+1]==a)))
                    cout<<"T"<<endl;
                else cout<<"F"<<endl;
            }
            else if(flag==3)//是父结点
            {
                int j=0;
                for(int i=1; i<=n; ++i)
                    if(heap[i]==a)
                    {
                        j=i;
                        break;
                    }
                if(j!=0&&((heap[j*2]==b||heap[j*2+1]==b)))
                    cout<<"T"<<endl;
                else cout<<"F"<<endl;
            }
            else if(flag==4)//是子结点
            {
                int j=0;
                for(int i=1; i<=n; ++i)
                    if(heap[i]==a)
                    {
                        j=i;
                        break;
                    }
                if(j!=0&&((heap[j/2]==b||heap[(j-1)/2]==b)))
                    cout<<"T"<<endl;
                else cout<<"F"<<endl;
            }
        }
    }