P1377 [TJOI2011]树的序

    • 123通过
    • 332提交
  • 题目提供者 elijahqi
  • 评测方式 云端评测
  • 标签 各省省选 2011 天津 高性能
  • 难度 提高+/省选-
  • 时空限制 1000ms / 128MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 体验新版界面

    最新讨论 显示

    推荐的相关题目 显示

    题目描述

    众所周知,二叉查找树的形态和键值的插入顺序密切相关。准确的讲:1、空树中加入一个键值k,则变为只有一个结点的二叉查找树,此结点的键值即为k;2、在非空树中插入一个键值k,若k小于其根的键值,则在其左子树中插入k,否则在其右子树中插入k。

    我们将一棵二叉查找树的键值插入序列称为树的生成序列,现给出一个生成序列,求与其生成同样二叉查找树的所有生成序列中字典序最小的那个,其中,字典序关系是指对两个长度同为n的生成序列,先比较第一个插入键值,再比较第二个,依此类推。

    输入输出格式

    输入格式:

    第一行,一个整数,n,表示二叉查找树的结点个数。第二行,有n个正整数,k1到kn,表示生成序列,简单起见,k1~kn为一个1到n的排列。

    输出格式:

    一行,n个正整数,为能够生成同样二叉查找数的所有生成序列中最小的。

    输入输出样例

    输入样例#1: 复制
    4
    1 3 4 2
    
    输出样例#1: 复制
    1 3 2 4

    说明

    对于20%的数据,n ≤ 10。

    对于50%的数据,n ≤ 100。

    对于100%的数据,n ≤ 100,000。

    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。