规范化数组元素的算法

Question

如果一个数组包含N个元素（元素可以重复），并且目标是在每次迭代中使所有元素都等于一个元素上的+1和另一个元素的-1，我们如何确定是否可以规范化数组？解决这个问题的最佳算法是什么？

Ex。

对于数组1 2 3，如果我在1上应用+1，在3上应用-1时，数组将变为2 2 2。这意味着它可以在1次迭代中实现。

对于数组1 2 1，不可能使所有元素相等。

Answer 1

首先，由于每次迭代都不会干扰求和，因此增加一个数字并减少另一个数字，因此最佳目标值将是平均值。

如果这个平均值是一个整数，您应该能够通过迭代来实现它，但是如果平均值是分数，那么您将无法实现它

步数将是每个数字与目标之间的距离之和除以2。

每一次迭代都会在目标之上和之下选择一个数字，并将运算应用于它们。

PS根据评论，如果你只想回答以下两个问题：

1. 能做到吗
2. 价值是什么

那么答案是：

1. 是的，只要平均数是一个整数
2. 在整个数组中重复的值是平均数

无论如何，如果您希望实际操作从输入到目标值，这里有一个更长的例子：

1 2 3 4 5 6 7 = 28, 28/7 = 4 (optimal target)
+           -
2 2 3 4 5 6 6
+           -
3 2 3 4 5 6 5
+           -
4 2 3 4 5 6 4
  +       -
4 3 3 4 5 5 4
  +       -
4 4 3 4 5 4 4
    +   -
4 4 4 4 4 4 4

6步，让我们从第一个数字开始计算距离：

1 2 3 4 5 6 7
3 2 1 0 1 2 3 = 12, divided by 2 = 6

以下是关于这个问题的评论中的例子：

 1  9 10 12  3  7 = 42 / 6 = 7 (optimal target)

距离：

 1  9 10 12  3  7
 6  2  3  5  4  0 = 20, divided by 2 = 10 (steps)
 1  9 10 12  3  7
 +  -              step 1
 2  8 10 12  3  7
 +  -              step 2
 3  7 10 12  3  7
 +     -           step 3
 4  7  9 12  3  7
 +     -           step 4
 5  7  8 12  3  7
 +     -           step 5
 6  7  7 12  3  7
 +        -        step 6
 7  7  7 11  3  7
          -  +     step 7
 7  7  7 10  4  7
          -  +     step 8
 7  7  7  9  5  7
          -  +     step 9
 7  7  7  8  6  7
          -  +     step 10
 7  7  7  7  7  7

下面是一个更像伪代码的算法描述：

1. 计算所有元素的总和
2. 计数所有元素
3. 如果AVERAGE（SUM/COUNT）不是整数，则解决方案不可能实现
4. STEPS=总和（ABS（数字N-平均值））/2
5. 每次迭代，选择一个低于平均值和一个高于平均值的数字
6. 对下面的数字应用+运算，对上面的数字应用-运算
7. 重复步骤5和6，直到达到目标