PAT – 第4页 – 柳婼の blog

[Java] 1003. Emergency (25)-PAT甲级

1003. Emergency (25)
As an emergency rescue team leader of a city, you are given a special map of your country. The map shows several scattered cities connected by some roads. Amount of rescue teams in each city and the length of each road between any pair of cities are marked on the map. When there is an emergency call to you from some other city, your job is to lead your men to the place as quickly as possible, and at the mean time, call up as many hands on the way as possible.

Input

Each input file contains one test case. For each test case, the first line contains 4 positive integers: N (<= 500) – the number of cities (and the cities are numbered from 0 to N-1), M – the number of roads, C1 and C2 – the cities that you are currently in and that you must save, respectively. The next line contains N integers, where the i-th integer is the number of rescue teams in the i-th city. Then M lines follow, each describes a road with three integers c1, c2 and L, which are the pair of cities connected by a road and the length of that road, respectively. It is guaranteed that there exists at least one path from C1 to C2.

Output

For each test case, print in one line two numbers: the number of different shortest paths between C1 and C2, and the maximum amount of rescue teams you can possibly gather.
All the numbers in a line must be separated by exactly one space, and there is no extra space allowed at the end of a line.

Sample Input
5 6 0 2
1 2 1 5 3
0 1 1
0 2 2
0 3 1
1 2 1
2 4 1
3 4 1
Sample Output
2 4
题目大意：n个城市m条路，每个城市有救援小组，所有的边的边权已知。给定起点和终点，求从起点到终点的最短路径条数以及最短路径上的救援小组数目之和。如果有多条就输出点权（城市救援小组数目）最大的那个~

PS：感谢github用户@fs19910227提供的pull request～

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.TreeSet;

public class Main {
    private static BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));

    static class Road implements Comparable<Road> {
        int fromCity, toCity, distance;

        Road(int fromCity, int toCity, int distance) {
            this.fromCity = fromCity;
            this.toCity = toCity;
            this.distance = distance;
        }

        @Override
        public int compareTo(Road o) {
            int compare = distance - o.distance;
            if (compare == 0) {
                compare = toCity - o.toCity;
                return compare == 0 ? fromCity - o.fromCity : compare;
            } else {
                return compare;
            }
        }
    }

    static class Node implements Comparable<Node> {
        int id, rescueTeams = 0, roadLength = 0;

        Node(int id, int rescueTeams) {
            this.id = id;
            this.rescueTeams = rescueTeams;
        }

        @Override
        public int compareTo(Node o) {
            int compare = roadLength - o.roadLength;
            return compare == 0 ? hashCode() - o.hashCode() : compare;
        }

        @Override
        public String toString() {
            return "Node{" +
                    "id=" + id +
                    ", rescueTeams=" + rescueTeams +
                    ", roadLength=" + roadLength +
                    '}';
        }
    }

    static class CityMap {
        final int cityNumbers, start_city, end_city, roadNumbers;
        final int[] rescues;
        final LinkedList<Road>[] roads;

        CityMap() throws IOException {
            int[] ints = readLine();
            this.cityNumbers = ints[0];
            this.roadNumbers = ints[1];
            this.start_city = ints[2];
            this.end_city = ints[3];
            rescues = readLine();
            roads = new LinkedList[cityNumbers];
            for (int i = 0; i < cityNumbers; i++) {
                roads[i] = new LinkedList<>();
            }

            for (int i = 0; i < roadNumbers; i++) {
                //读入路径
                ints = readLine();
                int start = ints[0], end = ints[1], length = ints[2];
                roads[start].add(new Road(start, end, length));
                roads[end].add(new Road(end, start, length));
            }
        }
    }

    private static int[] readLine() throws IOException {
        return Arrays.stream(reader.readLine().split(" "))
                .mapToInt(Integer::valueOf)
                .toArray();
    }

    public static void main(String[] args) throws IOException {
        final CityMap cityMap = new CityMap();
        final int start_city = cityMap.start_city;
        final int end_city = cityMap.end_city;
        int[] rescues = cityMap.rescues;

        boolean[] visited = new boolean[cityMap.cityNumbers];
        TreeSet<Node> nodes = new TreeSet<>();
        nodes.add(new Node(start_city, rescues[start_city]));
        int max_counts = 0;
        int max_rescue_teams = 0;
        int min_load_length = Integer.MAX_VALUE;
        while (!nodes.isEmpty()) {
            Node node = nodes.pollFirst();
            visited[node.id] = true;
            if (node.roadLength > min_load_length) break;
            if (node.id == end_city) {
                min_load_length = node.roadLength;
                max_counts++;
                max_rescue_teams = Math.max(max_rescue_teams, node.rescueTeams);
            }
            for (Road road : cityMap.roads[node.id]) {
                if (!visited[road.toCity]) {
                    Node newNode = new Node(road.toCity, node.rescueTeams + rescues[road.toCity]);
                    newNode.roadLength = node.roadLength + road.distance;
                    nodes.add(newNode);
                }
            }
        }

        System.out.println(max_counts + " " + max_rescue_teams);
    }
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

import java.io.BufferedReader;

import java.io.IOException;

import java.io.InputStreamReader;

import java.util.Arrays;

import java.util.LinkedList;

import java.util.TreeSet;

public class Main {

private static BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));

static class Road implements Comparable<Road> {

int fromCity, toCity, distance;

Road(int fromCity, int toCity, int distance) {

this.fromCity = fromCity;

this.toCity = toCity;

this.distance = distance;

}

@Override

public int compareTo(Road o) {

int compare = distance - o.distance;

if (compare == 0) {

compare = toCity - o.toCity;

return compare == 0 ? fromCity - o.fromCity : compare;

} else {

return compare;

}

static class Node implements Comparable<Node> {

int id, rescueTeams = 0, roadLength = 0;

Node(int id, int rescueTeams) {

this.id = id;

this.rescueTeams = rescueTeams;

}

@Override

public int compareTo(Node o) {

int compare = roadLength - o.roadLength;

return compare == 0 ? hashCode() - o.hashCode() : compare;

}

@Override

public String toString() {

return "Node{" +

"id=" + id +

", rescueTeams=" + rescueTeams +

", roadLength=" + roadLength +

'}';

}

static class CityMap {

final int cityNumbers, start_city, end_city, roadNumbers;

final int[] rescues;

final LinkedList<Road>[] roads;

CityMap() throws IOException {

int[] ints = readLine();

this.cityNumbers = ints[0];

this.roadNumbers = ints[1];

this.start_city = ints[2];

this.end_city = ints[3];

rescues = readLine();

roads = new LinkedList[cityNumbers];

for (int i = 0; i < cityNumbers; i++) {

roads[i] = new LinkedList<>();

}

for (int i = 0; i < roadNumbers; i++) {

//读入路径

ints = readLine();

int start = ints[0], end = ints[1], length = ints[2];

roads[start].add(new Road(start, end, length));

roads[end].add(new Road(end, start, length));

}

private static int[] readLine() throws IOException {

return Arrays.stream(reader.readLine().split(" "))

.mapToInt(Integer::valueOf)

.toArray();

}

public static void main(String[] args) throws IOException {

final CityMap cityMap = new CityMap();

final int start_city = cityMap.start_city;

final int end_city = cityMap.end_city;

int[] rescues = cityMap.rescues;

boolean[] visited = new boolean[cityMap.cityNumbers];

TreeSet<Node> nodes = new TreeSet<>();

nodes.add(new Node(start_city, rescues[start_city]));

int max_counts = 0;

int max_rescue_teams = 0;

int min_load_length = Integer.MAX_VALUE;

while (!nodes.isEmpty()) {

Node node = nodes.pollFirst();

visited[node.id] = true;

if (node.roadLength > min_load_length) break;

if (node.id == end_city) {

min_load_length = node.roadLength;

max_counts++;

max_rescue_teams = Math.max(max_rescue_teams, node.rescueTeams);

}

for (Road road : cityMap.roads[node.id]) {

if (!visited[road.toCity]) {

Node newNode = new Node(road.toCity, node.rescueTeams + rescues[road.toCity]);

newNode.roadLength = node.roadLength + road.distance;

nodes.add(newNode);

}

System.out.println(max_counts + " " + max_rescue_teams);

}

[Java] 1002. A+B for Polynomials (25)-PAT甲级

This time, you are supposed to find A+B where A and B are two polynomials.

Input
Each input file contains one test case. Each case occupies 2 lines, and each line contains the information of a polynomial: K N1 aN1 N2 aN2 … NK aNK, where K is the number of nonzero terms in the polynomial, Ni and aNi (i=1, 2, …, K) are the exponents and coefficients, respectively. It is given that 1 <= K <= 10，0 <= NK < … < N2 < N1 <=1000.

Output
For each test case you should output the sum of A and B in one line, with the same format as the input. Notice that there must be NO extra space at the end of each line. Please be accurate to 1 decimal place.

Sample Input
2 1 2.4 0 3.2
2 2 1.5 1 0.5
Sample Output
3 2 1.5 1 2.9 0 3.2

题目大意：计算A+B的和，A和B都是多项式

PS：感谢github用户@fs19910227提供的pull request～

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
    static class Polynomial {
        private static int MAX_SIZE = 1001;
        private double[] coefficients;

        Polynomial(String[] splits) {
            coefficients = new double[MAX_SIZE];
            for (int i = 1; i < splits.length; i += 2) {
                int exp = Integer.valueOf(splits[i]);
                coefficients[exp] = Double.valueOf(splits[i + 1]);
            }
        }

        Polynomial() {
            coefficients = new double[MAX_SIZE];
        }

        public Polynomial add(Polynomial other) {
            Polynomial result = new Polynomial();
            for (int i = 0; i < MAX_SIZE; i++) {
                double v = this.coefficients[i] + other.coefficients[i];
                v = Math.round(v * 10) / 10.0;
                if (v != 0.0) {
                    result.coefficients[i] = v;
                }
            }
            return result;
        }

        @Override
        public String toString() {
            StringBuilder stringBuilder = new StringBuilder();
            int size = 0;
            for (int i = coefficients.length - 1; i >= 0; i--) {
                double v = coefficients[i];
                if (v != 0.0) {
                    stringBuilder.append(i).append(" ").append(v).append(" ");
                    size++;
                }
            }
            stringBuilder.insert(0, size + " ");
            stringBuilder.deleteCharAt(stringBuilder.length() - 1);
            return stringBuilder.toString();
        }
    }

    private static BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));

    public static String[] readLine() throws IOException {
        return reader.readLine().split(" ");
    }

    public static void main(String[] args) throws IOException {
        Polynomial add = new Polynomial(readLine()).add(new Polynomial(readLine()));
        System.out.println(add);
    }
}

import java.io.BufferedReader;

import java.io.IOException;

import java.io.InputStreamReader;

public class Main {

static class Polynomial {

private static int MAX_SIZE = 1001;

private double[] coefficients;

Polynomial(String[] splits) {

coefficients = new double[MAX_SIZE];

for (int i = 1; i < splits.length; i += 2) {

int exp = Integer.valueOf(splits[i]);

coefficients[exp] = Double.valueOf(splits[i + 1]);

}

Polynomial() {

coefficients = new double[MAX_SIZE];

}

public Polynomial add(Polynomial other) {

Polynomial result = new Polynomial();

for (int i = 0; i < MAX_SIZE; i++) {

double v = this.coefficients[i] + other.coefficients[i];

v = Math.round(v * 10) / 10.0;

if (v != 0.0) {

result.coefficients[i] = v;

}

return result;

}

@Override

public String toString() {

StringBuilder stringBuilder = new StringBuilder();

int size = 0;

for (int i = coefficients.length - 1; i >= 0; i--) {

double v = coefficients[i];

if (v != 0.0) {

stringBuilder.append(i).append(" ").append(v).append(" ");

size++;

}

stringBuilder.insert(0, size + " ");

stringBuilder.deleteCharAt(stringBuilder.length() - 1);

return stringBuilder.toString();

}

private static BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));

public static String[] readLine() throws IOException {

return reader.readLine().split(" ");

}

public static void main(String[] args) throws IOException {

Polynomial add = new Polynomial(readLine()).add(new Polynomial(readLine()));

System.out.println(add);

}

PAT 1143. Lowest Common Ancestor (30) – 甲级

The lowest common ancestor (LCA) of two nodes U and V in a tree is the deepest node that has both U and V as descendants.
A binary search tree (BST) is recursively defined as a binary tree which has the following properties:
The left subtree of a node contains only nodes with keys less than the node’s key.
The right subtree of a node contains only nodes with keys greater than or equal to the node’s key.
Both the left and right subtrees must also be binary search trees.
Given any two nodes in a BST, you are supposed to find their LCA.
Input Specification:
Each input file contains one test case. For each case, the first line gives two positive integers: M (<= 1000), the number of pairs of nodes to be tested; and N (<= 10000), the number of keys in the BST, respectively. In the second line, N distinct integers are given as the preorder traversal sequence of the BST. Then M lines follow, each contains a pair of integer keys U and V. All the keys are in the range of int.
Output Specification:
For each given pair of U and V, print in a line “LCA of U and V is A.” if the LCA is found and A is the key. But if A is one of U and V, print “X is an ancestor of Y.” where X is A and Y is the other node. If U or V is not found in the BST, print in a line “ERROR: U is not found.” or “ERROR: V is not found.” or “ERROR: U and V are not found.”.
Sample Input:
6 8
6 3 1 2 5 4 8 7
2 5
8 7
1 9
12 -3
0 8
99 99
Sample Output:
LCA of 2 and 5 is 3.
8 is an ancestor of 7.
ERROR: 9 is not found.
ERROR: 12 and -3 are not found.
ERROR: 0 is not found.
ERROR: 99 and 99 are not found.

题目大意：给出一棵二叉搜索树的前序遍历，问结点u和v的共同最低祖先是谁～
分析：map<int, bool> mp用来标记树中所有出现过的结点，遍历一遍pre数组，将当前结点标记为a，如果u和v分别在a的左、右，或者u、v其中一个就是当前a，即(a >= u && a <= v) || (a >= v && a <= u)，说明找到了这个共同最低祖先a，退出当前循环～最后根据要求输出结果即可～
PS：30分的题目30行代码解决，1行1分，惊不惊喜？意不意外？（真的是水题啊…）

#include <iostream>
#include <vector>
#include <map>
using namespace std;
map<int, bool> mp;
int main() {
    int m, n, u, v, a;
    scanf("%d %d", &m, &n);
    vector<int> pre(n);
    for (int i = 0; i < n; i++) {
        scanf("%d", &pre[i]);
        mp[pre[i]] = true;
    }
    for (int i = 0; i < m; i++) {
        scanf("%d %d", &u, &v);
        for(int j = 0; j < n; j++) {
            a = pre[j];
            if ((a >= u && a <= v) || (a >= v && a <= u)) break;
        } 
        if (mp[u] == false && mp[v] == false)
            printf("ERROR: %d and %d are not found.\n", u, v);
        else if (mp[u] == false || mp[v] == false)
            printf("ERROR: %d is not found.\n", mp[u] == false ? u : v);
        else if (a == u || a == v)
            printf("%d is an ancestor of %d.\n", a, a == u ? v : u);
        else
            printf("LCA of %d and %d is %d.\n", u, v, a);
    }
    return 0;
}

#include <iostream>

#include <vector>

#include <map>

using namespace std;

map<int, bool> mp;

int main() {

int m, n, u, v, a;

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

vector<int> pre(n);

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

scanf("%d", &pre[i]);

mp[pre[i]] = true;

}

for (int i = 0; i < m; i++) {

scanf("%d %d", &u, &v);

for(int j = 0; j < n; j++) {

a = pre[j];

if ((a >= u && a <= v) || (a >= v && a <= u)) break;

}

if (mp[u] == false && mp[v] == false)

printf("ERROR: %d and %d are not found.\n", u, v);

else if (mp[u] == false || mp[v] == false)

printf("ERROR: %d is not found.\n", mp[u] == false ? u : v);

else if (a == u || a == v)

printf("%d is an ancestor of %d.\n", a, a == u ? v : u);

else

printf("LCA of %d and %d is %d.\n", u, v, a);

}

return 0;

}

PAT 1146. Topological Order (25) – 甲级

This is a problem given in the Graduate Entrance Exam in 2018: Which of the following is NOT a topological order obtained from the given directed graph? Now you are supposed to write a program to test each of the options.

Input Specification:
Each input file contains one test case. For each case, the first line gives two positive integers N (<= 1,000), the number of vertices in the graph, and M (<= 10,000), the number of directed edges. Then M lines follow, each gives the start and the end vertices of an edge. The vertices are numbered from 1 to N. After the graph, there is another positive integer K (<= 100). Then K lines of query follow, each gives a permutation of all the vertices. All the numbers in a line are separated by a space.
Output Specification:
Print in a line all the indices of queries which correspond to “NOT a topological order”. The indices start from zero. All the numbers are separated by a space, and there must no extra space at the beginning or the end of the line. It is graranteed that there is at least one answer.
Sample Input:
6 8
1 2
1 3
5 2
5 4
2 3
2 6
3 4
6 4
5
1 5 2 3 6 4
5 1 2 6 3 4
5 1 2 3 6 4
5 2 1 6 3 4
1 2 3 4 5 6
Sample Output:
3 4

题目大意：给一个有向图，判断给定序列是否是拓扑序列～
分析：用邻接表v存储这个有向图，并将每个节点的入度保存在in数组中。对每一个要判断是否是拓扑序列的结点遍历，如果当前结点的入度不为0则表示不是拓扑序列，每次选中某个点后要将它所指向的所有结点的入度-1，最后根据是否出现过入度不为0的点决定是否要输出当前的编号i～flag是用来判断之前是否输出过现在是否要输出空格的～judge是用来判断是否是拓扑序列的～

#include <iostream>
#include <vector>
using namespace std;
int main() {
    int n, m, a, b, k, flag = 0, in[1010];
    vector<int> v[1010];
    scanf("%d %d", &n, &m);
    for (int i = 0; i < m; i++) {
        scanf("%d %d", &a, &b);
        v[a].push_back(b);
        in[b]++;
    }
    scanf("%d", &k);
    for (int i = 0; i < k; i++) {
        int judge = 1;
        vector<int> tin(in, in+n+1);
        for (int j = 0; j < n; j++) {
            scanf("%d", &a);
            if (tin[a] != 0) judge = 0;
            for (int it : v[a]) tin[it]--;
        }
        if (judge == 1) continue;
        printf("%s%d", flag == 1 ? " ": "", i);
        flag = 1;
    }
    return 0;
}

#include <iostream>

#include <vector>

using namespace std;

int main() {

int n, m, a, b, k, flag = 0, in[1010];

vector<int> v[1010];

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

for (int i = 0; i < m; i++) {

scanf("%d %d", &a, &b);

v[a].push_back(b);

in[b]++;

}

scanf("%d", &k);

for (int i = 0; i < k; i++) {

int judge = 1;

vector<int> tin(in, in+n+1);

for (int j = 0; j < n; j++) {

scanf("%d", &a);

if (tin[a] != 0) judge = 0;

for (int it : v[a]) tin[it]--;

}

if (judge == 1) continue;

printf("%s%d", flag == 1 ? " ": "", i);

flag = 1;

}

return 0;

}

1145. Hashing – Average Search Time (25) – 甲级

The task of this problem is simple: insert a sequence of distinct positive integers into a hash table first. Then try to find another sequence of integer keys from the table and output the average search time (the number of comparisons made to find whether or not the key is in the table). The hash function is defined to be “H(key) = key % TSize” where TSize is the maximum size of the hash table. Quadratic probing (with positive increments only) is used to solve the collisions.
Note that the table size is better to be prime. If the maximum size given by the user is not prime, you must re-define the table size to be the smallest prime number which is larger than the size given by the user.
Input Specification:
Each input file contains one test case. For each case, the first line contains two positive numbers: MSize, N, and M, which are the user-defined table size, the number of input numbers, and the number of keys to be found, respectively. All the three numbers are no more than 104. Then N distinct positive integers are given in the next line. All the numbers in a line are separated by a space and are no more than 105.
Output Specification:
For each test case, in case it is impossible to insert some number, print in a line “X cannot be inserted.” where X is the input number. Finally print in a line the average search time for all the M keys, accurate up to 1 decimal place.
Sample Input:
4 5 4
10 6 4 15 11
11 4 15 2
Sample Output:
15 cannot be inserted.
2.8

题目大意：给定一个序列，用平方探测法解决哈希冲突，然后给出m个数字，如果这个数字不能够被插入就输出”X cannot be inserted.”，然后输出这m个数字的平均查找时间
分析：先找到大于tsize的最小的素数为真正的tsize，然后建立一个tsize长度的数组。首先用平方探测法插入数字a，每次pos = (a + j * j) % tsize，j是从0～tsize-1的数字，如果当前位置可以插入就将a赋值给v[pos]，如果一次都没有能够插入成功就输出”X cannot be inserted.”。其次计算平均查找时间，每次计算pos = (a + j * j) % tsize，其中j <= tsize，如果v[pos]处正是a则查找到了，则退出循环，如果v[pos]处不存在数字表示没查找到，那么也要退出循环。每次查找的时候，退出循环之前的j就是这个数字的查找长度。最后ans除以m得到平均查找时间然后输出～

#include <iostream>
#include <vector>
using namespace std;
bool isprime(int n) {
    if (n <= 1) return false;
    for (int i = 2; i * i <= n; i++)
        if (n % i == 0) return false;
    return true;
}
int main() {
    int tsize, n, m, a;
    scanf("%d %d %d", &tsize, &n, &m);
    while(!isprime(tsize)) tsize++;
    vector<int> v(tsize);
    for (int i = 0; i < n; i++) {
        scanf("%d", &a);
        int flag = 0;
        for (int j = 0; j < tsize; j++) {
            int pos = (a + j * j) % tsize;
            if (v[pos] == 0) {
                v[pos] = a;
                flag = 1;
                break;
            }
        }
        if (!flag) printf("%d cannot be inserted.\n", a);
    }
    int ans = 0;
    for (int i = 0; i < m; i++) {
        scanf("%d", &a);
        for (int j = 0; j <= tsize; j++) {
            ans++;
            int pos = (a + j * j) % tsize;
            if (v[pos] == a || v[pos] == 0) break;
        }
    }
    printf("%.1lf\n", ans * 1.0 / m);
    return 0;
}

#include <iostream>

#include <vector>

using namespace std;

bool isprime(int n) {

if (n <= 1) return false;

for (int i = 2; i * i <= n; i++)

if (n % i == 0) return false;

return true;

}

int main() {

int tsize, n, m, a;

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

while(!isprime(tsize)) tsize++;

vector<int> v(tsize);

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

scanf("%d", &a);

int flag = 0;

for (int j = 0; j < tsize; j++) {

int pos = (a + j * j) % tsize;

if (v[pos] == 0) {

v[pos] = a;

flag = 1;

break;

}

if (!flag) printf("%d cannot be inserted.\n", a);

}

int ans = 0;

for (int i = 0; i < m; i++) {

scanf("%d", &a);

for (int j = 0; j <= tsize; j++) {

ans++;

int pos = (a + j * j) % tsize;

if (v[pos] == a || v[pos] == 0) break;

}

printf("%.1lf\n", ans * 1.0 / m);

return 0;

}

PAT 1147. Heaps (30) – 甲级

In computer science, a heap is a specialized tree-based data structure that satisfies the heap property: if P is a parent node of C, then the key (the value) of P is either greater than or equal to (in a max heap) or less than or equal to (in a min heap) the key of C. A common implementation of a heap is the binary heap, in which the tree is a complete binary tree. (Quoted from Wikipedia at https://en.wikipedia.org/wiki/Heap_(data_structure))
Your job is to tell if a given complete binary tree is a heap.
Input Specification:
Each input file contains one test case. For each case, the first line gives two positive integers: M (<= 100), the number of trees to be tested; and N (1 < N <= 1000), the number of keys in each tree, respectively. Then M lines follow, each contains N distinct integer keys (all in the range of int), which gives the level order traversal sequence of a complete binary tree.
Output Specification:
For each given tree, print in a line “Max Heap” if it is a max heap, or “Min Heap” for a min heap, or “Not Heap” if it is not a heap at all. Then in the next line print the trees postorder traversal sequence. All the numbers are separated by a space, and there must no extra space at the beginning or the end of the line.

Sample Input:
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
Sample Output:
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

题目大意：给一个树的层序遍历，判断它是不是堆，是大顶堆还是小顶堆。输出这个树的后序遍历～
分析：30分大题，25行代码，一行代码一分……（(⊙o⊙)嗯） // 我为什么这么机智可爱又伶俐？
从后往前检查所有节点（除了根节点）和它的父节点的关系，判断是否破坏最大堆或者最小堆的性质，如果有不满足的情况将maxn或minn置为0，以此排除最大堆或者最小堆～

然后后序遍历，对于index结点分别遍历孩子index*2和右孩子index*2+1，遍历完左右子树后输出根结点～

#include <iostream>
using namespace std;
int a[1005], m, n;
void postOrder(int index) {
    if (index > n) return;
    postOrder(index * 2);
    postOrder(index * 2 + 1);
    printf("%d%s", a[index], index == 1 ? "\n" : " ");
}
int main() {
    scanf("%d %d", &m, &n);
    while (m--) {
        int minn = 1, maxn = 1;
        for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
        for (int i = 2; i <= n; i++) {
            if (a[i] > a[i / 2]) maxn = 0;
            if (a[i] < a[i / 2]) minn = 0;
        }
        if (maxn == 1) printf("Max Heap\n");
        else if (minn == 1) printf("Min Heap\n");
        else printf("Not Heap\n");
        postOrder(1);
    }
    return 0;
}

#include <iostream>

using namespace std;

int a[1005], m, n;

void postOrder(int index) {

if (index > n) return;

postOrder(index * 2);

postOrder(index * 2 + 1);

printf("%d%s", a[index], index == 1 ? "\n" : " ");

}

int main() {

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

while (m--) {

int minn = 1, maxn = 1;

for (int i = 1; i <= n; i++) scanf("%d", &a[i]);

for (int i = 2; i <= n; i++) {

if (a[i] > a[i / 2]) maxn = 0;

if (a[i] < a[i / 2]) minn = 0;

}

if (maxn == 1) printf("Max Heap\n");

else if (minn == 1) printf("Min Heap\n");

else printf("Not Heap\n");

postOrder(1);

}

return 0;

}