algorithm - 最小化分发糖果的步骤

Question

一圈有 n 个 child 。他们每个人都有一些糖果(可能是负数、正数或零)。他们一次可以给邻居一颗糖果。最终结果是他们都应该以最少的步骤获得零糖果。

假设我们有 4 个 child ，每个 child 都有 (-4, -2, 4, 2) 糖果，那么顺序就是

1. (-3, -2, 4, 1)
2. (-2, -2, 4, 0)
3. (-2, -1, 3, 0)
4. (-2, 0, 2, 0)
5. (-2, 1, 1, 0)
6. (-2, 2, 0, 0)
7. (-1, 1, 0, 0)
8. ( 0, 0, 0, 0)

这是一个可能的答案，我必须找到最少的步骤数。

• 循环1:查找邻居是否有正糖果，然后将其交给负糖果的邻居，直到糖果数为零，并将给定的糖果数相加求和。

  <

• 循环2:查找邻居的邻居是否有正糖果，然后将其交给负糖果的邻居，直到糖果数量为零并加2(给总和的糖果数量)。

• 等等。

我的解决方案的复杂性导致了 TLE。我可以做些什么来降低复杂性？

Answer 1

我认为您不需要详细地循环。将每个地方的糖果数写为 X1、X2、X3、X4。假设 X1 从它的左边收到 k 个糖果(即对于 X4)。在此之后它有 X1+k 个糖果，所以它必须将这个传递给它的右边。然后 X2 将有 X1 + X2 + k 个糖果，所以它必须把这个传给它的右边。然后 X3 将有 X1 + X2 + X3 + k 个糖果，所以它必须将这个传递给 X4。我们知道 X4 传递了 k 个糖果，这会检查(假设 X1 + X2 + X3 + X4 = 0，如果不是，则无解)。

这需要|k| + |X1 + k| + |X1 + X2 + k| + |X1 + X2 + X3 + k|步骤，所以如果我们猜测 k，我们就知道要采取多少步。 k的最佳值是多少？如果我们增加 k，如果有更多 +ve 项 X1 + X2 + ... k，我们会增加总和，如果有更多 -ve 项，则减少总和。所以 k 的最佳值是其中恰好一半的项 |k|、|X1 + k|.. 是 +ve 和恰好一半是 -ve 因为如果不是这种情况，我们可以增加或减少 k 以使事情更好 - 要选择的 k 值是 - 0、X1、X1 + X2、X1 + X2 + X3 的中位数。

我已经针对您的示例的 n=4 情况说明了这一点，但我希望您可以从中得出一般 n 的答案。