最小化在一个圆圈中分配糖果的步骤

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)

等等。

我的解决方案的复杂性导致了一个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+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的答案。