TouchStone
  请登录后使用
登录 注册
 系统首页  练习题库  考试列表  判题结果  信息发布  解题排行
  • 首页
  • 题库
  • P2919
  • 题目
  • P2919栈排序
    限制 : 时间限制 : 10000 MS   空间限制 : 265536 KB
    问题描述

    HMY现在碰到了一个棘手的问题,有 N 个整数需要排序。HMY手头能用的工具就是若干个栈。她需要依次处理这 N 个数,对于每个数,HMY能做以下两件事:
      1.新建一个栈,并将当前数作为这个栈中的唯一的数;
      2.将当前数放入已有的栈的栈顶。
    对所有的数处理完成之后,HMY将这些栈排序后依次弹出每个栈里的元素后就可以得到一个非降的序列。

    输入格式

    第一行包含一个整数N,表示整数的个数。
    接下来的N行每行包含一个整数Di(|Di|<=231-1),其中Di表示所需处理的整数。

    输出格式

    只包含一行,为HMY最少需要的栈的数目。

    样例输入

    6
    9
    3
    6
    0
    6
    3

    样例输出

    2

    提示

    样例解释:
    最终两个栈中元素分别为:
    栈1:9 6 6 3
    栈2:3 0
    所以,先输出栈2中的元素,再输出栈1中的元素,得到:0 3 3 6 6 9

    数据范围:
    对于30%的数据,N<=5000
    对于100%的数据,N<=200000


    来源  出处不明,2014重庆省队集训第三轮,感谢nodgd放题