最小化在圆形糖果中分发的步骤

Question

n的孩子围成一圈。他们每个人都有一些糖果(可能是负的，正的，也可能是零的)。他们可以一次给邻居一颗糖。最终的结果是，它们都应该在最小的步骤中有零的糖果。

假设我们有4个带有(-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+x1+kx1+ X2 +k双倍+x1+ X2 + X3 +k，所以如果我们猜到k，我们知道要执行多少步。k的最佳值是多少？如果我们增加k，如果有更多的+v项，X1 + X2 +.k，如果有更多的-ve项，则会减少。所以，k的最佳值是一个，其中的一半的条件都是\x1+k.因为如果不是这样的话，我们可以增减k来使事情变得更好，选择的k值是0，X1，X1 + X2，X1 + X2 + X3的中位数。

我已经为你的例子的n=4案例说明了这一点，但我希望你能从这个例子中找出一般n的答案。

Answer 2

采纳mcdowella的想法，并把它用我的话(因为我花了一段时间来理解它，请看here对这个话题的担忧)使它看起来如下。关键的洞察力是：

• 就像你可以拥有负性糖果一样，你也可以传递负性糖果。
• 在一个方向上传递负性糖果基本上就是在相反的方向上传递(正)糖果。
• 不管孩子有多少糖果，每个人都会以零收场。

这个实现如下:选择一个任意的子图开始(在下面的图中，我有5个子，而不是4个)，我们选择一个任意的方向(在我们的例子中是逆时针方向)，然后开始传递。每个孩子都必须摆脱所有的糖果(正负)才能达到零。儿童A有-2糖果，所以我们把它传递给儿童B之后，B有-5，所以我们把它传递给孩子C，现在，孩子C有-4糖果，然后传递给D，等等。这是第二个图表，所有糖果在13个动作中为零。

​

​

哨兵图不是最优的。我们观察到，在中心图中传递的所有糖果都是负值(除了E->A pass)，而且我们可以在上添加或减去第一次传递:如果A->B pass是+5而不是-2，那么所有的传球都会由7递增，而E->A pass将是7而不是0，而A最终仍然没有糖果。因此，我们寻求一个可以调整所有传递的数字，从而使所有传递的绝对值之和最小化。在最后一个图表中我们看到，如果将+2添加到所有传递中，则所有传递的绝对值之和为7。举个例子，如果我们添加了+3，其总和就会更大。因此，我们试图在所有传递中添加一个常数，以最小化所有传递的绝对值之和。

如果有人认为我重新告诉mcdowella的想法不应该出现在这里，我很乐意删除。

Answer 3

这里应用的一种元方法是采用投票算法，并使其基于事件。我什么意思？

保持一个循环链接列表，其中包含赠品者(糖果>0 )和接受者(糖果<0 )。还维护一个优先级队列，其中包含每个相邻的(在列表中，而不是在圆圈中)的条目，给者-接受者对，其关键是给予者和接受者之间的距离。

现在，不要一次递增一段距离，而是使用优先级队列来找出下一件有趣的事情。每次送礼人对问题解决后，一个或两个孩子都会退出列表，这就需要O(1)簿记和队列插入。