A16656 | $Make it Zigzag$

时间限制1s

内存限制256MB

通过 / 提交0/0

题目描述

长度为 $m$ 的任意整数数组 $b$ 如果对于所有 $i$（$1 \le i < m$）满足以下条件，则被认为是“awesome”（极棒）的： - 如果 $i$ 是奇数，则 $b_i < b_{i+1}$。 - 如果 $i$ 是偶数，则 $b_i > b_{i+1}$。 换句话说，数组需满足如下不等式：$b_1 < b_2 > b_3 < b_4 \ldots$ 给定一个长度为 $n$ 的正整数数组 $a$。你可以按照任意顺序、任意多次执行以下两种操作： - 操作 $1$：选择一个整数 $i$（$1 \le i \le n$），令 $a_i := \max(a_1, \ldots, a_i)$，即将 $a_i$ 替换为前缀最大值。 - 操作 $2$：选择一个整数 $i$（$1 \le i \le n$），然后将 $a_i$ 减少 $1$。 请你求出使 $a$ 成为“awesome”数组所需执行操作 $2$ 的最少次数。注意：你不需要最小化执行操作 $1$ 的次数。

每组测试包含多个测试用例。第一行输入测试用例的数量 $t$（$1 \le t \le 10^4$）。接下来每组测试用例包含： 第一行输入一个整数 $n$（$2 \le n \le 2 \times 10^5$），表示数组 $a$ 的长度。 第二行输入 $n$ 个整数 $a_1,a_2,\ldots,a_n$（$1 \le a_i \le 10^9$）。 所有测试用例中 $n$ 的总和不超过 $2 \times 10^5$。

对于每组测试用例，输出使 $a$ 成为“awesome”数组所需执行操作 $2$ 的最小次数。

输入 #1

7
5
1 4 2 5 3
4
3 3 2 1
5
6 6 6 6 6
7
1 2 3 4 5 6 7
3
3 2 1
2
1 2
9
65 85 19 53 21 79 92 29 96

输出 #1

C++ 编辑器

输入

输出