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