• 周六. 8月 20th, 2022

5G编程聚合网

5G时代下一个聚合的编程学习网

热门标签

洛谷 P1377 [TJOI2011]树的序(笛卡尔树)

admin

11月 28, 2021

传送门


解题思路

仔细阅读题目,发现按照顺序插入每一个节点,且按照二叉搜索树的规则。
于是满足这两个条件其实就是笛卡尔树。
但是注意这里的x是读入的数,y是读入的数的下标。
构建完笛卡尔树后,其先序遍历的x值就是最终的ans。
(按照样例画个图就很显然了)

AC代码

#include<iostream>
#include<algorithm>
#include<cstring>
#include<stack>
using namespace std;
const int maxn=1e5+5;
int n,a[maxn],l[maxn],r[maxn];
stack<int> s;
void print(int u){
	if(u==0) return;
	cout<<u<<" ";
	print(l[u]);
	print(r[u]);
}
int main()
{
    ios::sync_with_stdio(false);
    cin>>n;
    for(int i=1;i<=n;i++){
    	int x;
    	cin>>x;
    	a[x]=i;
	}
	for(int i=1;i<=n;i++){
		while(!s.empty()&&a[s.top()]>a[i]) l[i]=s.top(),s.pop();
		if(!s.empty()) r[s.top()]=i;
		s.push(i);
	}
	int x;
	while(!s.empty()) x=s.top(),s.pop();
	print(x);
    return 0;
}

发表回复

您的电子邮箱地址不会被公开。