题目详解

问题重述

给定一个长度为 $n$ 的正整数数组 $a$，通过两种操作使其变成"awesome"数组：

• 操作1：将 $a_i$ 变为前缀最大值 $\max(a_1,\dots,a_i)$（不限次数）
• 操作2：将 $a_i$ 减少 $1$（需要最小化次数）

目标：最小化操作2的次数。

关键观察

1. Awesome数组的定义

数组 $b$ 满足：

即奇数位置需要小于相邻位置，偶数位置需要大于相邻位置。

2. 操作1的作用

操作1可以增加某个位置的值（变为前缀最大值），且可以多次使用。
这意味着我们可以任意提高数组中的某些值（只要不超过前缀最大值）。

3. 优化策略

根据标程的思路：

• 首先对所有偶数下标使用操作1（使其尽可能大）
• 经过这样处理后，所有偶数位置的值都无法再增加（因为已经等于到该位置的前缀最大值）
• 此时只需要考虑奇数位置，通过操作2减少它们的值

为什么只考虑奇数位置？

对于awesome数组：

• 奇数位置 $i$：需要小于 $a_{i-1}$ 和 $a_{i+1}$（相邻偶数位置）
• 偶数位置 $j$：需要大于 $a_{j-1}$ 和 $a_{j+1}$（相邻奇数位置）

由于我们已经将偶数位置最大化，它们自然会大于相邻的奇数位置（只要我们适当减小奇数位置）。
因此，只需调整奇数位置的值。

算法实现

标程的具体步骤：

1. 预处理前缀最大值

   $$pre[i] = \max(a_0, a_1, \dots, a_i)$$

2. 遍历所有奇数下标（$i = 0, 2, 4, \dots$） 对于每个奇数位置 $i$：

   • 考虑左边相邻偶数位置（如果存在）：$a[i] - pre[i-1]$
   • 考虑右边相邻偶数位置（如果存在）：$a[i] - pre[i+1]$
   • 取两者中的最大值作为需要减小的基准

3. 计算操作2次数 对于位置 $i$，需要满足：

   $$a_i < \min(a_{i-1}, a_{i+1})$$

   由于偶数位置已经被最大化，$a_{i-1} = pre[i-1]$，$a_{i+1} = pre[i+1]$
   因此需要：

   $$a_i \le \min(pre[i-1], pre[i+1]) - 1$$

   如果当前 $a_i$ 不满足，需要减少的次数为：

   $$a_i - (\min(pre[i-1], pre[i+1]) - 1) = a_i - \min(pre[i-1], pre[i+1]) + 1 $$

   标程中计算：

   $$dif = \max(a_i - pre[i-1], a_i - pre[i+1])$$

   注意：当 $dif = -1$ 时，意味着 $a_i$ 已经小于两个相邻值，不需要操作。

边界处理

• 对于 $i=0$（第一个元素），只考虑右边相邻
• 对于 $i=n-1$（最后一个元素且 $n$ 为奇数），只考虑左边相邻
• 标程将 $dif$ 初始化为 $-1$，然后取最大值，最后加 $1$ 得到需要减小的次数

复杂度分析

• 时间复杂度：$O(n)$ 每个测试用例
• 空间复杂度：$O(n)$ 存储前缀最大值

示例验证

以第二个测试用例 $[3,3,2,1]$ 为例：

• 前缀最大值：$pre = [3,3,3,3]$
• 奇数下标：$i=0,2$
  • $i=0$：$dif = \max(3-3, 3-3) = 0$，需要 $0+1=1$ 次
  • $i=2$：$dif = \max(2-3, 2-3) = -1$，需要 $0$ 次
• 总操作次数：$1$，与示例输出一致。

正确性证明

1. 可行性：通过先对偶数下标使用操作1，我们可以任意提高偶数位置的值，这不会影响操作2的最小次数（因为操作2只减少值）。

2. 最优性：对于每个奇数位置 $i$，它必须小于两个相邻的偶数位置。由于偶数位置已经最大化，我们无法让它们变小来满足条件，只能减小 $a_i$。每个奇数位置独立，因此分别计算最小值再求和就是最优解。

3. 边界处理：两端的奇数位置只需要考虑一个相邻偶数，算法通过条件判断正确处理了边界。