TouchStone
  请登录后使用
登录 注册
 系统首页  练习题库  考试列表  判题结果  问题讨论与解答  统计信息与排名
  • 首页
  • 题库
  • P3713
  • 题目
  • P3713雪人
    限制 : 时间限制 : - MS   空间限制 : 265536 KB
    评测说明 : 时限1000ms
    问题描述

    Description

    wy和wjk是好朋友。

    今天他们在一起聊天,突然聊到了以前一起唱过的《雪人》。

    “说到雪人,我给你讲一个故事吧。”

    “嗯?”

    “从前有N个雪人排成一排,他们有的高,有的矮,众所周知,雪人是一个有强迫症的种族,于是他们希望他们可以按照由矮到高的顺序排成一排,于是他们想到了冒泡排序,他们每次会选一个雪人,然后把他与他右边的雪人比较,如果他比较高,他就和右边的雪人互换位置,然后再与右边的雪人比较,直到某一次比较的时候,右边的雪人比他高,或者右边已经没有雪人了,他就停下来,然后雪人们会再选出一个雪人进行上面的程序,直到所有雪人都按照由矮到高的顺序站好,他们想知道,最少有多少个雪人会被选出来。可是他们数学实在是太差了。。。”

    “这实在是太简单了!”

    “哦,那你说说”

    “唔。。。N太大了,我需要写代码算一下。。。”

    [简化版题目描述]

    给定一个长度为N的序列,每次操作可以任意选择一个数,这个数和它右边的数比大小,如果这个数比较大,就和右边的数交换,然后和右边的数接着比大小直到某一次它右边的数比他大或者他右边没有数了。求最小的操作次数使得序列变为升序。

    输入格式

    第一行一个整数N代表雪人的数量

    接下来一行N个整数,第i个整数代表第i个雪人的高度

    输出格式

    一个整数,表示最少需要选出来的雪人的数量

    样例输入

    5
    5 1 2 3 4

    样例输出

    1

    提示

    【样例1解释】

    把第一个选出来就好了

    【数据范围】

    对于30%的数据,有1 ≤ N ≤ 2500;

    对于100%的数据,有1 ≤ N ≤ 1000000。

    雪人的高度是1到N的一个排列


    来源  源自nodgd