### 三、解题思路与实现 现在有一队小朋友，他们以正整数数组表示身高，例如 `{5,3,1,2,3}`。目标是将他们调整为“高”“矮”“高”“矮”交替排列的形式，其中第一个位置为“高”。每次移动的距离定义为移动前后位置的差值，要求移动距离总和最小。 解决该问题的核心在于动态规划或贪心策略的使用，以最小化移动距离。一种有效的方法是： - **预处理排序**：将原始数组排序，以便后续查找最优位置。 - **动态规划**：定义 `dp[i][j]` 表示前 `i` 个小朋友中，第 `i` 个小朋友放在第 `j` 个位置时的最小移动距离。 - **状态转移**：通过比较当前和前一个位置的身高关系，决定是否满足“高矮交替”的要求，并更新状态。 以下是 Python 实现代码： ```python def min_move_distance(heights): n = len(heights) sorted_heights = sorted(heights) pos_map = {h: i for i, h in enumerate(sorted_heights)} # 原始身高到排序后索引的映射 # dp[i][j] 表示前i个小朋友中，第i个放在排序后第j个位置的最小移动距离 dp = [[float('inf')] * n for _ in range(n)] # 初始化第一个小朋友 for j in range(n): dp[0][j] = abs(heights[0] - sorted_heights[j]) # 初始移动距离 for i in range(1, n): for j in range(n): for k in range(n): # 检查是否满足“高矮交替”的条件 if (i % 2 == 0 and sorted_heights[j] >= sorted_heights[k]) or \ (i % 2 == 1 and sorted_heights[j] <= sorted_heights[k]): dp[i][j] = min(dp[i][j], dp[i-1][k] + abs(heights[i] - sorted_heights[j])) return min(dp[n-1]) # 返回最后一个小朋友的最小移动距离 ``` #### 示例输入与输出 ```python # 示例输入 heights = [5, 3, 1, 2, 3] print(min_move_distance(heights)) # 输出应为最小移动距离 ``` #### 特点与优化 - **时间复杂度**：`O(n^3)`，其中 `n` 是小朋友数量。可以通过剪枝或贪心优化降低复杂度。 - **空间复杂度**：`O(n^2)`，用于存储动态规划表。 - **关键点**：排序后的位置选择是关键，确保每次插入都满足“高矮交替”的条件[^5]。 ---