PAT 1. 二叉树结点模拟
原题链接
简单
作者:
流动的音符
,
2024-04-17 12:55:27
,
所有人可见
,
阅读 2
#pragma GCC optimize(3,"Ofast","inline")
#pragma comment(linker, "/STACK:1024000000,1024000000")
#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
typedef long long ll;
#define int long long
#define ld long double
int tree[1 << 19];
int n,m;
int find(int u)//找出以u为根的子树的最大值
{
if(u >= m) return 0;
int t = max(find(u * 2),find(u * 2 + 1));
if(t > tree[u]) return t;
return tree[u];
}
signed main()
{
cin>>n;
m = (1 << (n + 1));//m - 1为最大下标
for(int i = n;i > 0;i--)//j为左节点编号,k为该层有几个左节点
for(int j = 1 << i,k = 1 << (i - 1);k;k--,j+=2)
scanf("%d",&tree[j]);//先将值放在对应的左节点上
scanf("%d",&tree[1]);//根节点
for(int i = 0;i < n;i++)//
{
int h = 1 << i;//该层第一个节点的编号
for(int j = 0;j < (1 << i);j++)
{
int now = h + j;//节点编号
if(tree[now] < tree[now * 2])//赢的人比输的人的能力值小,无解
{
puts("No Solution");
return 0;
}
tree[now * 2 + 1] = tree[now];//先放右节点上
int l = find(now * 2),r = find(now * 2 + 1);
//l,r分别为左右子树的最大值
if(tree[now * 2] != l || tree[now] != r)
//左右节点不是左右子树的最大值
{
swap(tree[now * 2],tree[now * 2 + 1]);//换一下看看
l = find(now * 2),r = find(now * 2 + 1);
if(l != tree[now * 2] || r != tree[now *2 + 1])//还不是,则无解
{
puts("No Solution");
return 0;
}
}
}
}
for(int i = 1 << n;i < m;i++)//输出最后一层
printf("%d%s",tree[i],(i == m - 1 ? "\n" : " "));
return 0;
}