题目大意

有 $N$ 个营员，身高分别为 $1$ 到 $N$，站在 $N$ 级台阶上。初始时第 $i$ 级台阶上站着身高为 $H_i$ 的营员。

要求通过交换相邻台阶上的营员，使得对于所有 $i$ ($1 \le i \le N-1$)，满足：

$$a_i < a_{i+1} + 2$$

其中 $a_i$ 是第 $i$ 级台阶上营员的最终身高。

求最小的交换次数。

算法思路

关键观察

满足条件的排列具有特殊的结构：最终排列由若干个连续递减的段拼接而成，且段首递增。

例如：$[3,2,1,5,4]$ 是合法的，包含段 $[3,2,1]$ 和 $[5,4]$。

动态规划解法

设 $f[i]$ 表示将身高 $1$ 到 $i$ 的营员安排好的最小交换次数。

状态转移：

$$f[i] = \min_{0 \le j < i} \{ f[j] + \text{cost}(j+1, i) \} $$

其中 $\text{cost}(l, r)$ 表示将身高 $l$ 到 $r$ 的营员作为一个连续递减段放置所需的交换次数。

代价计算

代价由两部分组成：

1. 外部逆序：当前段 $[j+1, i]$ 与已安排段 $[1, j]$ 之间的逆序对数量
2. 内部逆序：当前段内部按目标顺序排列所需的逆序对数量

通过预处理二维前缀和数组，可以在 $O(1)$ 时间内计算任意段的代价。

复杂度分析

• 时间复杂度：$O(N^2)$
• 空间复杂度：$O(N^2)$

总结

本题的核心在于发现最终排列的段结构性质，然后通过动态规划枚举所有可能的段划分。利用前缀和技巧快速计算逆序对数量，将复杂度优化到 $O(N^2)$，能够处理 $N \le 5000$ 的数据规模。