A7010 | 得到山形数组的最少删除次数
时间限制1s
内存限制128MB
通过 / 提交0/0
题目描述
我们定义数组 $a$ 是 山形数组 当且仅当它满足以下条件：
1. 数组长度 $n \ge 3$。
2. 存在某个下标 $i$（$0 i n - 1$），使得：
$$a_0 a_1 \dots a_{i - 1} a_i$$
$$a_i a_{i + 1} \dots a_{n - 1}$$
换句话说，山形数组的元素先严格递增，达到一个峰值后，再严格递减。
现在给你一个整数数组 $a$，请你返回将 $a$ 变成 山形数组 所需的 最少 删除次数。
题目保证 $a$ 在删除一些元素后，一定能得到一个山形数组。
1. 数组长度 $n \ge 3$。
2. 存在某个下标 $i$（$0 i n - 1$），使得：
$$a_0 a_1 \dots a_{i - 1} a_i$$
$$a_i a_{i + 1} \dots a_{n - 1}$$
换句话说，山形数组的元素先严格递增，达到一个峰值后，再严格递减。
现在给你一个整数数组 $a$，请你返回将 $a$ 变成 山形数组 所需的 最少 删除次数。
题目保证 $a$ 在删除一些元素后，一定能得到一个山形数组。
输入格式
第一行包含一个整数 $n$，表示数组 $a$ 的长度。
第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$，表示数组的元素。
第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$，表示数组的元素。
输出格式
输出一个整数，表示最少删除次数。
输入输出样例
输入 #1
3 1 3 1
输出 #1
0
输入 #2
8 2 1 1 5 6 2 3 1
输出 #2
3
【样例解释 1】
数组
【样例解释 2】
一种可行的方法是将下标为 0，1 和 5 的元素删除，剩余元素为
删除的元素为
【数据范围】
对于 $100\%$ 的数据，满足：
- $3 \le n \le 1000$
- $1 \le a_i \le 10^9$
- 题目保证输入数据中一定存在合法的山形子序列。
数组
[1, 3, 1] 本身就是山形数组，所以不需要删除任何元素。【样例解释 2】
一种可行的方法是将下标为 0，1 和 5 的元素删除，剩余元素为
[1, 5, 6, 3, 1]，这是一个山形数组。删除的元素为
2, 1, 2。【数据范围】
对于 $100\%$ 的数据，满足：
- $3 \le n \le 1000$
- $1 \le a_i \le 10^9$
- 题目保证输入数据中一定存在合法的山形子序列。
C++ 编辑器
输入
输出
可保存默认模板；新题优先使用已保存模板。
当前快捷键仅展示，暂不支持修改。
- 撤销
Ctrl / ⌘ + Z - 重做
Ctrl / ⌘ + Y - 查找
Ctrl / ⌘ + F - 全选
Ctrl / ⌘ + A - 复制
Ctrl / ⌘ + C - 剪切
Ctrl / ⌘ + X - 粘贴
Ctrl / ⌘ + V - 自动排版
工具栏排版按钮 - 草稿保存
编辑时自动保存到本机
历史
提交记录
状态说明时间源码
AI
作答助手
你好，我是作答助手。可以问思路、复杂度、样例含义或代码报错原因；不会直接给出完整 AC 代码。
确定要清空代码吗？