PAT甲级1147.

目录

A1147

题目

样例

输入:

3 8
98 72 86 60 65 12 23 50
8 38 25 58 52 82 70 60
10 28 15 12 34 9 8 56

输出:

Max Heap
50 60 65 72 12 23 86 98
Min Heap
60 58 52 38 82 70 25 8
Not Heap
56 12 34 28 9 8 15 10

思路和坑点

　　思路：
　　可以偷懒借助现成的库函数进行判定是不是堆，然后获取后序序列，也可以再获取后序序列的同时进行判定是否满足堆的要求。

AC代码

#include<bits/stdc++.h>
using namespace std;
int n,m;                            //m组数据，n个数值
int cnt=0;                          //格式控制计数器
vector<int> v;                      //存放序列
void Judge();                       //判断堆
void getpos(int root);              //后序序列
int main(){    
#ifdef ONLINE_JUDGE    
#else    
    freopen("1.txt", "r", stdin);    
#endif    
    scanf("%d%d",&m,&n);
    v.resize(n);
    for(int i=0;i<m;i++)            //依次判断每组数据
        Judge();
    return 0;    
}
void Judge(){
    cnt=0;
    for(int i=0;i<n;i++)
        scanf("%d",&v[i]);          //创建序列，并使用库函数直接判断是不是堆，需要C++11及以上标准支持
    if(is_heap(v.begin(),v.end(),less<int>()))
        puts("Max Heap");
    else if(is_heap(v.begin(),v.end(),greater<int>()))
        puts("Min Heap");
    else
        puts("Not Heap");
    getpos(0);                      //后序序列
    putchar('\n');
}
void getpos(int root){              //递归后序遍历
    if(root>=n) return;             //遇到空结点这返回
    getpos(root*2+1);               //下标从0开始则2n+1为左子树，2n+2为右子树
    getpos(root*2+2);
    if(cnt) putchar(' ');
    printf("%d",v[root]);           //输出当前结点
    cnt++;
}