algorithm - 找到最小操作数

Question

给定两个整数数组，我们必须找到将一个数组转换为另一个数组的最少操作数。

操作如下:

如果我们将数组的一个元素减 1，则所有其他元素都加 1。

我们必须找到将一个数组更改为另一个数组的此类操作的最少数量。

例子假设初始数组是 3 2 2
最终数组是 4 5 3

所需的最少操作数为 5。

解释:3 2 2 -> 2 3 3 -> 3 4 2 -> 2 5 3 -> 3 4 4 -> 4 5 3

Answer 1

令 N 为数组的大小，A 和 B。对于 N=1，则可以进行任何变换，步数为 abs(A[0] - B[0])。对于N=2，每次操作增加一个数字并减少另一个数字。那么对于存在的解决方案，我们必须有 B[1] = A[1] - B[0] + A[0]，并且操作数是 abs(A[0] - B[0])(或等效abs(A[1] - B[1])).

对于 N > 2，考虑数组中所有元素的总和。每一步减少一个元素1，并增加N-1个元素1。所以总数增加N-2。

因此，如果可以使用这样的操作将数组 A 转换为数组 B，则步骤数将为 (sum(B) - sum(A))/(N-2)。称这个为 T。

操作通勤，因此要计算转换是否可能，只需计算出每个元素递减多少次就足够了。如果第 i 个元素递减 n_i 次，则它递增 T-n_i 次。所以 B[i] = A[i] - n_i + T - n_i，因此 n_i = (A[i] - B[i] + T)/2。

这就是我们需要的一切:如果 (sum(B) - sum(A)) 可以被 N-2 整除，并且调用 T = (sum(B) - sum(A)/(N-2) ), 我们还需要 A[i] - B[i] + T 可以被 2 整除并且每个 i 都是非负的。

请注意，在任何情况下都没有选择:如果存在解决方案，则它在操作顺序方面是唯一的。