POJ 2201

红太狼 2022-01-28 09:59 147阅读 0赞

## 题目：笛卡尔树：笛卡尔树中的每个节点有两个数据域k，a，对于数据域k，满足二叉搜索树性质，对于数据域a，满足最小堆性质。给出N个节点，1<=N<=50000，每个节点由一对k，a构成，判断能否根据这些节点构建一颗笛卡尔树，如果可以构建则输出构造出的笛卡尔树，否则输出“NO”。 ##

## 解题思路：首先，根据N个节点，肯定可以构造出一颗笛卡尔树。 ##

## 参考博客：[https://www.cnblogs.com/pushing-my-way/archive/2012/08/24/2653709.html][https_www.cnblogs.com_pushing-my-way_archive_2012_08_24_2653709.html] ##

## [https://blog.csdn.net/lijiecsu/article/details/7490666][https_blog.csdn.net_lijiecsu_article_details_7490666] ##

## [https://blog.csdn.net/faithdmc/article/details/37604441][https_blog.csdn.net_faithdmc_article_details_37604441] ##

## 代码： ##

#include <cstdio>
    #include <algorithm>
    using namespace std;
     
    struct S{
    int id,key,val,parent,l,r;
    }node[50005];
     
    bool cmp(struct S a,struct S b)
    {
        return a.key<b.key;
    }
     
    int stk[50005],top,p[50005],l[50005],r[50005];
     
    void build(int n)//因为已经按key值升序排序了，所以后面加入的节点要么成为某个节点的右儿子，要么让根节点成为自己的左儿子
    {
        int i;
        top=0;
        stk[top]=1;
        for(i=2;i<=n;i++)
        {
            while(top>=0 && node[stk[top]].val>node[i].val) top--;
            if(top>-1)//如果找到一个不大于自己的节点，就成为该节点的右儿子，还要注意让该节点原来的右儿子变成自己的左儿子(key比其大并且小于其val)
            {
                node[i].parent=stk[top];
                node[node[stk[top]].r].parent=i;
                node[i].l=node[stk[top]].r;
                node[stk[top]].r=i;
            }
            else//如果没找到不大于自己的节点，就变成新的根
            {
                node[stk[0]].parent=i;
                node[i].l=stk[0];
            }
            stk[++top]=i;
        }
    }
     
    int main()
    {
        int n,i;
        while(~scanf("%d",&n))
        {
            for(i=1;i<=n;i++)
            {
                scanf("%d%d",&node[i].key,&node[i].val);
                node[i].id=i;
                node[i].parent=node[i].l=node[i].r=0;//初始化
            }
            sort(node+1,node+n+1,cmp);
            build(n);
            for(i=1;i<=n;i++)
            {
                p[node[i].id]=node[node[i].parent].id;
                l[node[i].id]=node[node[i].l].id;
                r[node[i].id]=node[node[i].r].id;
            }
            printf("YES\n");
            for(i=1;i<=n;i++) printf("%d %d %d\n",p[i],l[i],r[i]);
        }
        return 0;
    }

[https_www.cnblogs.com_pushing-my-way_archive_2012_08_24_2653709.html]: https://www.cnblogs.com/pushing-my-way/archive/2012/08/24/2653709.html
[https_blog.csdn.net_lijiecsu_article_details_7490666]: https://blog.csdn.net/lijiecsu/article/details/7490666
[https_blog.csdn.net_faithdmc_article_details_37604441]: https://blog.csdn.net/faithdmc/article/details/37604441