如何以最小成本将数组所有元素转换为零？

首先得明确问题核心：我们要处理数组里的正数（盈余，需要减少）和负数（赤字，需要增加），通过三种操作的组合找到最低总成本。关键在于对比**转移操作（操作3）和直接处理（操作1+操作2）**的成本，同时算出转移的最小可能开销。

步骤1：统计盈余与赤字 #

遍历数组，分别整理两个列表：

• 盈余列表：把每个正数元素的位置，重复该元素的值次数（比如位置0的元素是2，就往列表里加两次0）
• 赤字列表：把每个负数元素的位置，重复该元素绝对值的次数（比如位置1的元素是-2，就往列表里加两次1）
  同时计算总盈余S_pos（所有正数的和）和总赤字S_neg（所有负数绝对值的和）。

步骤2：计算两种候选成本 #

我们需要对比两种方案的成本，取最小值：

方案A：完全不转移

所有盈余用操作1直接减1，成本是S_pos * B；所有赤字用操作2直接加1，成本是S_neg * L。总成本为：

cost_A = S_pos * B + S_neg * L

方案B：尽可能转移（取最小转移成本）

首先，最多能转移的单位数是k = min(S_pos, S_neg)。我们要算出这k个单位转移的最小成本：

• 由于盈余和赤字列表是按数组遍历顺序生成的（从左到右），直接按顺序一一配对两个列表的元素，计算每个配对的|pos_surplus - pos_deficit| * M，求和得到min_transfer_cost。
• 剩下的盈余（S_pos - k）用操作1处理，剩下的赤字（S_neg - k）用操作2处理。
• 这里要注意：如果单个单位的转移成本|pos_surplus - pos_deficit| * M比直接处理的成本B + L高，那不如直接处理这个单位。所以我们可以直接对比min_transfer_cost和k*(B+L)，取较小的那个作为转移部分的成本。

方案B的总成本为：

transfer_part = min(min_transfer_cost, k * (B + L))
cost_B = transfer_part + (S_pos - k) * B + (S_neg - k) * L

步骤3：取最优解 #

最终的最低成本就是min(cost_A, cost_B)。

为什么这样高效？ #

数组元素的绝对值范围很小（-10到10），所以盈余和赤字列表的最大长度是1e5 * 10 = 1e6，遍历计算的时间复杂度是O(1e6)，完全符合题目对效率的要求，而且不需要复杂的数据结构，只需要线性遍历和简单的列表操作。

示例验证 #

拿题目给出的测试用例举例：
输入数组[2, -2, 1, 0, -1, -1]，B=20，L=150，M=30。

• 盈余列表：[0,0,2]（位置0有2个盈余，位置2有1个）
• 赤字列表：[1,1,4,5]（位置1有2个赤字，位置4有1个，位置5有1个）
• k = min(3,4) =3
• 按顺序配对计算转移成本：|0-1|*30 + |0-1|*30 + |2-4|*30 = 30+30+60=120
• 对比转移成本120和3*(20+150)=510，显然120更小
• 剩余赤字是4-3=1，成本1*150=150
• cost_B=120+150=270，和题目输出一致
• cost_A=320 +4150=60+600=660，显然270更优

边界情况考虑 #

1. 当B+L <= M * max_distance（max_distance是数组最大位置差）：此时转移完全不划算，直接选cost_A即可
2. 当S_pos = S_neg：所有单位都可以考虑转移，取转移成本和S_pos*(B+L)的最小值
3. 当数组全为0：成本为0

内容的提问来源于stack exchange，提问作者tusharRawat