Processing math: 100%
编程题
                ### 问题描述

现在有一个由 n 个房间组成的迷宫,每个房间内都藏有宝藏,每个房间都有一个整数值,代表这个房间内宝藏的价值。现在小蓝准备探索这个迷宫,在迷宫中寻找宝藏。小蓝进入迷宫后偶然发现迷宫中有一个隐藏任务,完成隐藏任务就可以获得绝世宝藏,现在小蓝想请你帮助她获得绝世宝藏。

现有一个长度为 n 的数组 aa[i] 表示第 i 个房间内宝藏的价值,小蓝现在可以拿走任意次数的宝藏(可以是 0 次),每次拿走宝藏需要先选择一个整数 x ,然后将所有价值等于 x 的宝藏都拿走,然后房间内宝藏价值变为 0 。小蓝只要通过拿走宝藏,使得数组 a 变成一个非递减序列,就可以获取绝世宝藏。请你帮助小蓝算出最少需要拿走几次宝藏可以获取绝世宝藏?

输入格式

输入一共两行,第一行 1 个整数 n ,代表迷宫中房间的数目。

第二行输入 n 个非负整数 a1,a2,a3,...,an 代表初始每个房间的宝藏价值。

输出格式

输出一行一个整数代表小蓝最少需要拿取宝藏的次数。

样例输入

5
3 1 5 3 2

样例输出

3

说明

对于样例需要拿取 3 次宝藏,可以使得数组 a 变为非递减序列。例如:

第一次拿取价值为 3 的宝物,数组变为 [0,1,5,0,2]

第二次拿取价值为 1 的宝物,数组变为 [0,0,5,0,2]

第三次拿取价值为 5 的宝物,数组变为 [0,0,0,0,2]

此时数组变成了一个非递减序列。

评测数据规模

对于 60% 的评测数据 1n103,1a[i]n

对于 100% 的评测数据 1n105,1a[i]n

查看答案
赣ICP备20007335号-2