1649 堆路径 PAT 1155
作者:
NikoNairre
,
2023-12-01 17:16:59
,
所有人可见
,
阅读 80
#include <iostream>
#include <vector>
#include <limits.h>
#include <algorithm>
using namespace std;
const int N = 1010;
int a[N * 4];
vector<int> cpath;
vector<vector<int>> all_path;
int n;
bool has_max = false, has_min = false;
bool is_max = true, is_min = true;
void init()
{
for (int i = 0; i < 4 * N; i++ ) a[i] = INT_MAX;
}
void dfs(int u) //using dfs to record
{
if (a[u] == INT_MAX) return;
int c = a[u]; //actual node val
cpath.push_back(c);
if (a[u * 2] == INT_MAX and a[u * 2 + 1] == INT_MAX) { //leave node
all_path.push_back(cpath); //record current path
}
/*
search right (2i + 1) first, then search left(2i)
in this way, the final path will be recorded from left to right due to backdate
*/
if (a[u * 2 + 1] != INT_MAX) {
dfs(u * 2 + 1); //search right
cpath.pop_back();
}
if (a[u * 2] != INT_MAX) {
dfs(u * 2); //search left
cpath.pop_back(); //backdate
}
}
int check_order(vector<int> &cur) {
int res = 0;
bool max_heap = true, min_heap = true;
for (int i = 0; i < cur.size() - 1; i++ ) {
if (cur[i] < cur[i + 1]) {
max_heap = false; //max heap must store in non-ascending order;
}
if (cur[i] > cur[i + 1]) { //min heap must store in non-decreasing order;
min_heap = false;
}
}
/*
res = 0 means current branch doesn't equal to a heap
res = 1 means it's equal to a max heap
res = 2 means it's equal to a min heap
*/
if (max_heap) res = 1;
if (min_heap) res = 2;
return res;
}
int main()
{
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
cin >> n;
init();
for (int i = 1; i <= n; i++ ) cin >> a[i];
dfs(1);
int judge = 0;
for (int i = 0; i < all_path.size(); i++ ) {
if (i) cout << endl;
judge = check_order(all_path[i]);
if (judge == 1) {
has_max = true;
}
if (judge == 2) {
has_min = true;
}
for (int j = 0; j < all_path[i].size(); j++ ) {
if (j) cout << " ";
cout << all_path[i][j];
}
}
cout << endl;
if (!judge or (has_max and has_min)) {
cout << "Not Heap";
}
else {
if (has_max) {
for (int i = 0; i < all_path.size(); i++ ) {
if (check_order(all_path[i]) != 1) {
is_max = false;
break;
}
}
if (is_max) {
cout << "Max Heap";
}
else {
cout << "Not Heap";
}
}
else if (has_min) {
for (int i = 0; i < all_path.size(); i++ ) {
if (check_order(all_path[i]) != 2) {
is_min = false;
break;
}
}
if (is_min) {
cout << "Min Heap";
}
else {
cout << "Not Heap";
}
}
}
return 0;
}