题意理解
给定一个序列,根据这个序列求小根堆的笛卡尔树
笛卡尔树的性质见 https://www.cnblogs.com/LiuRunky/p/Cartesian_Tree.html
思路
1. 上图的性质中的大概意思是,笛卡尔树的每一个根节点为当前序列中的最小值,而左二子必须在根节点的左边,右儿子必须在根节点的右边。
2. 构建笛卡尔树:找到当前序列的最小值作为根节点,根节点左边的序列再构建一棵树作为左子树,右边的序列构建的数作为右子树。但这里不需要构建,只需要输出就好了
3. 层序遍历一棵树,用队列来写,队列中保存的是当前需要构建笛卡尔树的序列坐标范围,出队一个点,找到当前序列的最小值,输出,然后将左序列入队,再将右序列入队,直到队为空。
CPP
#include <iostream>
using namespace std;
typedef pair<int, int> PII;
const int N = 35, INF = 0x3f3f3f3f;
int n, x[N];
int main()
{
cin >> n;
for(int i = 0; i < n; i ++) scanf("%d", &x[i]);
PII q[N * 10];
int hh = 0, tt = -1;
q[++ tt] = {0, n - 1};
while(hh <= tt)
{
PII t = q[hh ++];
int l = t.first, r = t.second, pos = l, v = x[l];
if(l > r) continue;
for(int i = l; i <= r; i ++)
{
if(x[i] < v)
{
v = x[i];
pos = i;
}
}
printf("%d ", v);
q[++ tt] = {l, pos - 1};
q[++ tt] = {pos + 1, r};
}
return 0;
}