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

题目链接: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 ;
}




### L2-012 判断 测试点分析与解题思路 #### 题目概述 L2-012PAT(Programming Ability Test)的一道经典题目,主要考察结构的理解及其性质的应用。该题目要求实现一个基于小顶的操作流程,并通过一系列命题来验证的状态是否满足特定条件。 根据描述,每组测试的第一行包含两个正整数 \( N \) 和 \( M \),分别代表插入到初始为空的小顶中的元素数量和需要判断的命题数目[^2]。随后提供了一列待插入的整数值范围在 [-10000, 10000] 内的数据集合。接着有 \( M \) 行命题,用于评估当前状态下的某些特性。 --- #### 小顶定义及基本操作 小顶是一种完全二叉树形式的数据结构,在数组中存储时具有如下特点: - **父节点小于等于子节点**:对于任意非叶子节点 \( i \),其左孩子位于位置 \( 2i+1 \),右孩子位于位置 \( 2i+2 \),并且满足 \( A[i] \leq A[2i+1] \) 及 \( A[i] \leq A[2i+2] \)[^1]。 构建小顶的核心在于维护上述性质。当新元素加入时需执行上滤(percolate up 或 bubble up),而删除根节点则涉及下滤(percolate down 或 sink down)过程。 --- #### 解题步骤解析 以下是针对此问题的一个高效解决方案框架: 1. **初始化空** 使用列表 `heap` 存储数据,其中索引从 0 开始计数以便简化计算逻辑。另外准备辅助函数完成插入、调整等基础功能。 2. **逐个插入元素并保持序** 对于给定序列中的每一个数字调用 insert 方法将其纳入 heap 数组同时确保整体仍维持为合法的小顶形态。具体做法是在每次新增项后沿路径向上比较直至找到合适的位置或者到达顶端为止。 3. **处理查询请求** 接下来按照输入顺序逐一读取各条命题语句并对当前形成的实例作出相应判定回应。“IsRoot(x)” 类型询问某指定值 x 是否处于顶部;“ParentSmallerThanChild(y,z)” 形式的断言检查 y 节点作为 z 的父亲节点是否存在且确实更小等等。 4. **输出最终结果** 根据之前所得结论按原样打印 Yes/No 字符串至标准输出流结束整个算法运行周期。 下面展示了一个 Python 实现版本供参考: ```python class MinHeap: def __init__(self): self.heap = [] def parent(self, idx): return (idx - 1) // 2 def left_child(self, idx): return 2 * idx + 1 def right_child(self, idx): return 2 * idx + 2 def swap(self, i, j): self.heap[i], self.heap[j] = self.heap[j], self.heap[i] def sift_up(self, idx): while idx != 0 and self.heap[self.parent(idx)] > self.heap[idx]: p = self.parent(idx) self.swap(p, idx) idx = p def push(self, value): self.heap.append(value) self.sift_up(len(self.heap)-1) def process_queries(heap_instance, queries): results = [] for query in queries: parts = query.split() if parts[0] == 'IsRoot': val_to_check = int(parts[1]) result = ('Yes' if len(heap_instance.heap)>0 and heap_instance.heap[0]==val_to_check else 'No') elif parts[0].startswith('Parent'): child_val = int(parts[-1]) # last part is always the child node's value try: pos = heap_instance.heap.index(child_val) if pos==0 or not ((pos%2)==1 or (pos%2)==0 ): raise ValueError par_pos = (pos-1)//2 res_cond = heap_instance.heap[par_pos]<child_val result=('Yes'if res_cond else 'No') except Exception as e: result='No' results.append(result) return "\n".join(results) # Example usage based on problem statement structure. import sys input_data = sys.stdin.read().splitlines() line_idx=iter(range(len(input_data))) next_line=lambda : input_data[next(line_idx)] nm_values = list(map(int,next_line().strip().split())) N,M = nm_values[:2] elements=[int(i)for i in next_line().strip().split()] queries=[next_line()for _ in range(M)] my_heap = MinHeap() for elem in elements: my_heap.push(elem) final_output = process_queries(my_heap, queries) print(final_output,end='') ``` --- #### 测试点分析 为了更好地理解可能遇到的各种情况,这里列举了一些常见的测试场景及其应对策略: 1. **边界条件检测** - 插入单个元素的情况应能正确识别它既是根也是唯一成员。 - 当尝试访问不存在的孩子节点时应回复 No。 2. **常规大小的行为验证** - 多层次嵌套关系下的父子对比准确性至关重要。 3. **极端规模挑战** - 输入接近最大限制 (\( N=1000,\ M=20\)) 下性能表现如何? 以上这些方面都需要特别注意以保证提交代码能够顺利通过所有潜在考验环节。 ---
评论
添加红包

请填写红包祝福语或标题

红包个数最小为10个

红包金额最低5元

当前余额3.43前往充值 >
需支付:10.00
成就一亿技术人!
领取后你会自动成为博主和红包主的粉丝 规则
hope_wisdom
发出的红包
实付
使用余额支付
点击重新获取
扫码支付
钱包余额 0

抵扣说明:

1.余额是钱包充值的虚拟货币,按照1:1的比例进行支付金额的抵扣。
2.余额无法直接购买下载,可以购买VIP、付费专栏及课程。

余额充值