在一个圆形区域内分发糖果的最小步骤

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（给糖果的数量）。 以此类推。

我的方案复杂度太高了，导致超时。我该如何减少复杂度？

- kanz

---

请尝试引用您使用的在线评测机。 - Alexander

n的最大值为10000，时间限制为3秒。这是我在面试街上参加学院编码比赛时遇到的问题。我没有能够解决它，但很好奇答案是什么。 - kanz

负面糖果？那些可怜的孩子！ - j_random_hacker

TLE = "颞叶癫痫"？ - angelatlarge

Answer 1

我认为你不需要详细循环计算。将每个位置上的糖果数量写成X1、X2、X3、X4等形式。假设X1从左边（即X4）得到k个糖果，然后它就有了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，那么当有更多的正数项X1+X2+...+k时，总和会增加，而当有更多的负数项时，则减少。因此，最佳的k值是使得|k|、|X1+k|等一半项为正数，另一半为负数，因为如果这不是这种情况，我们可以增加或减少k以获得更好的结果，所以要选择的k值是0、X1、X1+X2、X1+X2+X3的中位数。

我已经介绍了你例子的n=4情况，但我希望你可以从中推出一般情况的答案。

- mcdowella

---

啊！我15分钟前就已经用完全相同的方法解决了这个问题，但现在才能登录。加一分。干得好 :-) - Knoothe

当我意识到k可以是负数，表示从右到左的转移时，一切都豁然开朗了。假设我们知道从左边的孩子转移给第i个孩子的糖果数量，这个数量和第i个孩子最初拥有的糖果数量决定了他们必须传递多少糖果给右边的孩子，以便自己最终得到0颗糖果。理论上，我们可以猜测k大于所有正数糖果总数（导致糖果“出现”），但这样的尝试解决方案永远不会被选择，因为它们不能是最优解。太好了！ - j_random_hacker

很棒的解决方案，@angelatlarge 的解释非常有必要。 - Jagadeesh Pulamarasetti

Answer 2

采用 mcdowella 的想法，并用我的话表达(因为我花了一段时间才理解它，参见这里对此话题的一些争论)，如下所示。关键见解是：

• 就像你可以拥有负糖果一样，你也可以传递负糖果。
• 在一个方向上传递负糖果基本上就是在相反的方向上传递（正）糖果。
• 无论孩子有多少糖果，每个人最终都会得到零。

我们实现它的方法是：选择任意一个孩子开始（在下面的图中是A孩子，我有5个孩子而不是4个），然后选择一个任意的方向（我们的情况是逆时针方向），开始传递。每个孩子都必须摆脱所有的糖果（正数或负数）以达到零。所以A孩子有-2糖果，所以我们把它传给B孩子。之后B孩子有-5糖果，所以我们把它传给C孩子。现在C孩子有-4糖果，传给D孩子，依此类推。这是第二张图，所有的糖果在13次移动后都变成零了。

中间的图不是最优的。我们观察到，在中间的图中传递的所有糖果都是负数（除了E->A的传递），而且我们可以任意添加或减少第一次传递的值：如果A->B传递的是+5而不是-2，那么所有的传递都会增加7，而 E->A 的传递将会变成 7 而不是 0，在最后 A 还是没有糖果。因此，我们寻找一个可以调整所有传递的数字，使所有传递的绝对值之和最小。在最后一张图中，我们可以看到，如果我们对所有传递的值都加上 +2，所有传递的绝对值之和为 7。举例来说，如果我们加上 +3，那么和就会更大。因此，我们要添加一个常数到所有传递中，使所有传递的绝对值之和最小。

P.S. 如果有人认为我重新讲述mcdowella的想法不该出现在这里，我会很乐意删除。

- angelatlarge

---

这是一个很好的解释 :) 我也花了一些时间才明白 mcdowella 的答案中“负数 k 等于糖果沿相反方向传递”的想法。 - j_random_hacker

谢谢！是的，我只是不确定是否要发布这个：我不想窃取mcdowella的知识产权，但我认为这个想法很棒，也许有另一种解释方法。 - angelatlarge

你在一开始就清楚地给了他/她信用 - 我想这是任何人需要做的！更多的解释==好 :) - j_random_hacker

非常好的解释！ - Jagadeesh Pulamarasetti

Answer 3

一种适用于这里的元方法是将轮询算法转化为基于事件的算法。我的意思是什么？

维护一个循环链表，其中包含赠送者（拥有 >0 糖果的孩子）和接收者（拥有 <0 糖果的孩子）。还需要维护一个优先队列，其中包含每个相邻（在列表中而非在圆圈中）的赠送者-接收者对的条目，其键是赠送者和接收者之间的距离。

现在，不要逐个增加距离，而是使用优先队列来找出下一个有趣的事情发生的位置。每次解决赠送者-接收者对时，一个或两个孩子会从列表中退出，这需要 O(1) 的簿记和队列插入。

- David Eisenstat