TouchStone
  Please Login
Login Sign Up
 Homepage  Problem Set  Course  Examinations  Submissions  Discussions  Statistics
  • Home
  • Problem Set
  • P2919
  • Problem
  • P2919栈排序
    Limits : Time Limit : 10000 MS   Memory Limit : 265536 KB
    Description

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

    Input Format

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

    Output Format

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

    Sample Input

    6
    9
    3
    6
    0
    6
    3

    Sample Output

    2

    Hint

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

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


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