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

Question

我们得到一个整数的数组，我们希望将所有元素转换为具有最小总成本的。

我们可以对数组元素执行3次操作：

如果成本为B

• Increase，则L

• Decrease a元素减少1，在loc i中，

1. 元素减少1，在i-j-j* M

中，元素增加1。

示例测试用例：

输入

  [2, -2, 1, 0, -1, -1]
  B = 20, L = 150, M = 30 

输出

270

解释:

Increase by 2 at loc 1 and decrease by 2 at loc 0, cost incurred : 2 * |1 - 0| * 30 = 60
Increase by 1 at loc 4 and decrease by 1 at loc 2, cost incurred : 1 * |4 - 2| * 30 = 60
Increase by 1 at loc 5, cost incurred : 1 * 150 = 150
So total min cost: 60 + 60 + 150 = 270

约束:

1

-10 < Ai < 10

1 < B，L< 10^8

1 如何有效地解决这一问题?

Answer 1

从这个问题上看，有几件事要考虑。哪种操作在降低成本方面最有效。有三个选项，B、L和n_M，其中n是两个元素之间的“距离”。当成本小于L和B运算(150 + 20)或n= 5时，n_M是值得使用的。因为5*M= 150。然而，唯一使用这种方法的方法是，当有一个正反两部分时，最多只有5个元素分开。所以这将是第一次测试。如果这些标准得到满足，这种情况将产生最低的成本。

其次最好的情况是成本B，其中元素是正的，在+-5元素中没有负元素。

最后一种情况是随着成本L的增加而增加。

所有这些都可以通过多种方式进行测试。我现在考虑的方法是创建一个包含11个元素的队列。用上述标准测试中间元素，然后弹出并推送FIFO，遍历数组。这些只是我最初想让你开始的想法。