线性动态规划：最小操作次数使数组元素相等（每次操作可对任意元素加1或减1，但每次操作有固定代价）
字数 1850 2025-12-21 15:13:39

线性动态规划：最小操作次数使数组元素相等（每次操作可对任意元素加1或减1，但每次操作有固定代价）

题目描述

给定一个整数数组 nums 和一个整数 cost。你可以对数组中的任意元素进行如下操作：

  • 每次操作可以选择一个元素，将其值 增加 1 或 减少 1。
  • 每次操作（无论是加还是减）的代价固定为 cost。

目标是使数组中 所有元素相等，并返回所需的最小总代价。如果无法使所有元素相等，则返回 -1（但在这个基本版本中，总是可以通过足够多的操作使元素相等）。

思路分析

这个问题本质上是一个 优化中位数 的问题，但带有每次操作的固定代价。
设最终所有元素都变成某个值 target。
对于任意元素 nums[i]，从 nums[i] 变成 target 需要的操作次数为：

\[\text{ops}_i = |nums[i] - target| \]

总代价为：

\[\text{总代价} = \text{ops}_i \times cost \]

对所有元素求和：

\[\text{总代价} = cost \times \sum_{i=1}^n |nums[i] - target| \]

因此，问题转化为：
找到一个整数 target，使得 \(\sum |nums[i] - target|\) 最小，然后乘以 cost 就是答案。
这是经典的 最小化绝对差和 问题，最优的 target 是 nums 的 中位数（当数组长度为奇数时，中位数唯一；当长度为偶数时，中位数可以是中间两个数之间的任意整数）。

为什么是中位数？

简要说明：

  • 假设数组排序后为 \(a_1 \le a_2 \le \dots \le a_n\)。
  • 要最小化 \(f(t) = \sum |a_i - t|\)，它是一个关于 \(t\) 的分段线性凸函数，最小值出现在中位数位置。
  • 如果 \(n\) 是奇数，中位数是 \(a_{(n+1)/2}\)。
  • 如果 \(n\) 是偶数，\(t\) 可以是区间 \([a_{n/2}, a_{n/2+1}]\) 中的任意整数，通常取任意一个（比如 \(a_{n/2}\) 或 \(a_{n/2+1}\)）即可。

解题步骤

  1. 排序数组：将 nums 按升序排序。
  2. 找到中位数：
    • 如果 n 是奇数，中位数是 nums[n//2]。
    • 如果 n 是偶数，中位数可以取 nums[n//2] 或 nums[n//2 - 1]，两者计算结果相同（因为目标是最小化绝对差和）。
  3. 计算总操作次数：
    遍历数组，对每个元素计算它与中位数的绝对差，并累加。
  4. 计算总代价：
    总操作次数 × 每次操作的代价 cost。

举例说明

例：
nums = [1, 2, 3, 4, 5]，cost = 2
排序后数组已经是 [1,2,3,4,5]
n=5，中位数是 nums[5//2] = nums[2] = 3
操作次数 = |1-3| + |2-3| + |3-3| + |4-3| + |5-3| = 2+1+0+1+2 = 6
总代价 = 6 × 2 = 12

验证：
如果所有元素都变成 3，需要的操作是：

  • 1→3：2 次操作，代价 4
  • 2→3：1 次操作，代价 2
  • 3→3：0 次操作，代价 0
  • 4→3：1 次操作，代价 2
  • 5→3：2 次操作，代价 4
    总代价 = 4+2+0+2+4 = 12 ✔

为什么不能用平均数？

因为这里是 绝对差 的和，不是平方差。
对于绝对差，中位数是最优的；对于平方差，平均数是最优的。
可以简单验证：
数组 [1, 2, 100]

  • 中位数是 2，绝对差和 = 1+0+98 = 99
  • 平均数是 ≈34.33，取整 34，绝对差和 = 33+32+66 = 131 > 99

所以这里必须用中位数。

算法复杂度

  • 排序：O(n log n)
  • 求中位数：O(1)
  • 计算总操作次数：O(n)
    总复杂度 O(n log n)，空间复杂度 O(1) 或 O(n)（取决于是否原地排序）。

扩展思考

如果每次操作的代价不是固定的，而是与元素值的变化方向有关（例如加1的代价和减1的代价不同），问题会更复杂，可能需要用加权中位数或动态规划解决。但在这个基础版本中，固定代价使得问题简化为经典的中位数问题。

线性动态规划：最小操作次数使数组元素相等（每次操作可对任意元素加1或减1，但每次操作有固定代价） 题目描述 给定一个整数数组 nums 和一个整数 cost 。你可以对数组中的任意元素进行如下操作： 每次操作可以选择一个元素，将其值 增加 1 或 减少 1 。 每次操作（无论是加还是减）的代价固定为 cost 。 目标是使数组中 所有元素相等 ，并返回所需的最小总代价。如果无法使所有元素相等，则返回 -1（但在这个基本版本中，总是可以通过足够多的操作使元素相等）。 思路分析 这个问题本质上是一个 优化中位数 的问题，但带有每次操作的固定代价。 设最终所有元素都变成某个值 target 。 对于任意元素 nums[i] ，从 nums[i] 变成 target 需要的操作次数为： \[ \text{ops}_ i = |nums[ i ] - target| \] 总代价为： \[ \text{总代价} = \text{ops} i \times cost \] 对所有元素求和： \[ \text{总代价} = cost \times \sum {i=1}^n |nums[ i ] - target| \] 因此， 问题转化为 ： 找到一个整数 target ，使得 \(\sum |nums[ i] - target|\) 最小，然后乘以 cost 就是答案。 这是经典的 最小化绝对差和 问题，最优的 target 是 nums 的 中位数 （当数组长度为奇数时，中位数唯一；当长度为偶数时，中位数可以是中间两个数之间的任意整数）。 为什么是中位数？ 简要说明： 假设数组排序后为 \(a_ 1 \le a_ 2 \le \dots \le a_ n\)。 要最小化 \(f(t) = \sum |a_ i - t|\)，它是一个关于 \(t\) 的分段线性凸函数，最小值出现在中位数位置。 如果 \(n\) 是奇数，中位数是 \(a_ {(n+1)/2}\)。 如果 \(n\) 是偶数，\(t\) 可以是区间 \([ a_ {n/2}, a_ {n/2+1}]\) 中的任意整数，通常取任意一个（比如 \(a_ {n/2}\) 或 \(a_ {n/2+1}\)）即可。 解题步骤 排序数组 ：将 nums 按升序排序。 找到中位数 ： 如果 n 是奇数，中位数是 nums[n//2] 。 如果 n 是偶数，中位数可以取 nums[n//2] 或 nums[n//2 - 1] ，两者计算结果相同（因为目标是最小化绝对差和）。 计算总操作次数 ： 遍历数组，对每个元素计算它与中位数的绝对差，并累加。 计算总代价 ： 总操作次数 × 每次操作的代价 cost 。 举例说明 例： nums = [ 1, 2, 3, 4, 5 ]，cost = 2 排序后数组已经是 [ 1,2,3,4,5 ] n=5，中位数是 nums[ 5//2] = nums[ 2 ] = 3 操作次数 = |1-3| + |2-3| + |3-3| + |4-3| + |5-3| = 2+1+0+1+2 = 6 总代价 = 6 × 2 = 12 验证： 如果所有元素都变成 3，需要的操作是： 1→3：2 次操作，代价 4 2→3：1 次操作，代价 2 3→3：0 次操作，代价 0 4→3：1 次操作，代价 2 5→3：2 次操作，代价 4 总代价 = 4+2+0+2+4 = 12 ✔ 为什么不能用平均数？ 因为这里是 绝对差 的和，不是平方差。 对于绝对差，中位数是最优的；对于平方差，平均数是最优的。 可以简单验证： 数组 [ 1, 2, 100 ] 中位数是 2，绝对差和 = 1+0+98 = 99 平均数是 ≈34.33，取整 34，绝对差和 = 33+32+66 = 131 > 99 所以这里必须用中位数。 算法复杂度 排序：O(n log n) 求中位数：O(1) 计算总操作次数：O(n) 总复杂度 O(n log n)，空间复杂度 O(1) 或 O(n)（取决于是否原地排序）。 扩展思考 如果每次操作的代价不是固定的，而是 与元素值的变化方向有关 （例如加1的代价和减1的代价不同），问题会更复杂，可能需要用加权中位数或动态规划解决。但在这个基础版本中，固定代价使得问题简化为经典的中位数问题。