有n孩子围成一圈。他们每个人都有一些糖果（可能是负数、正数或零）。他们可以一次给邻居一个糖果。最终结果是，他们都应该在最少的步骤中拥有零糖果。
假设我们有 4 个孩子拿着(-4, -2, 4, 2)糖果，那么序列将是
这是一个可能的答案，我必须找到最少的步骤数。
循环1：查找邻居是否有正糖果，然后将其给与负糖果的邻居，直到糖果数量等于0，然后将给定的糖果数量加到总和中。
循环2：查找邻居的邻居是否有正糖果，然后将其交给有负糖果的邻居，直到糖果数量等于0，然后加2（给和的糖果数量）。
等等。
我的解决方案的复杂性导致了 TLE。我能做些什么来降低复杂性？
我认为您不需要详细循环。将每个位置的糖果数量写为 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 的答案。
将 mcdowella的想法付诸实践（因为我花了一段时间才理解它，请参阅此处了解有关此主题的一些手稿），使其看起来如下。主要见解是：
这个实现如下：选择一个任意的孩子开始（下图中的孩子A，我有5个孩子而不是4个），我们选择一个任意方向（在我们的例子中是逆时针方向），然后开始通过。每个孩子都必须摆脱所有糖果（正面或负面）才能归零。所以孩子 A 有-2糖果，所以我们把它传递给孩子 B。之后孩子 B 有 -5 糖果，所以我们把它传递给孩子 C。现在孩子 C 有 -4 糖果，然后把它传递给 D，依此类推。这是第二张图，所有糖果在 13 步中都为零。
发送者图不是最佳的。我们观察到在中心图中传递的所有糖果都是负数（保存 E->A 传递）并且我们可以随意从第一次传递中添加或减去：如果 A->B 传递而+5不是-2，那么所有传递将增加7，并且 E->A pass 将7不是 0，最后 A 仍然没有糖果。所以我们寻找一个数字，通过它我们可以调整所有通道，使所有通道的绝对值之和最小化。在最后一张图中，我们看到，如果我们将+2所有通道相加，则所有通道的绝对值之和为 7。作为说明，如果我们添加+3总和会更大。因此，我们寻求为所有通道添加一个常数，以最小化所有通道的绝对值之和。
PS 如果有人认为我不应该在这里重新讲述mcdowella的想法，我很乐意删除。
一种适用于此的元方法是采用一种轮询算法并使其基于事件。我是什么意思？
维护一个循环链接列表，其中包含给予者（糖果 >0 的孩子）和接受者（糖果 <0 的孩子）。还维护一个优先级队列，其中包含每个相邻（在列表中，而不是在圆圈中）给予者-接受者对的条目，其关键是给予者和接受者之间的距离。
现在，不是一次增加一个距离，而是使用优先级队列来找出下一个发生的有趣事情。每次解决给予者-接受者对时，一个或两个孩子都会从列表中退出，这需要 O(1) 的簿记和队列插入。