最大限度地减少分布在一个圆圈中的糖果的步骤

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 + k | + | X1 + X2 + k | + | X1 + X2 + X3 + k | 步骤,所以如果我们猜测k我们知道要采取多少步骤.k的最佳价值是多少？如果我们增加k,如果有更多+ ve项X1 + X2 + ... k,则增加总和,如果有更多-ve项则减少.因此,k的最佳值是其中正好一半的| k |,| X1 + k | ..是+ ve且正好是一半 - 因为如果不是这种情况我们可以增加或减少k来制作更好的事情 - 要选择的k的值是 - 中位数0,X1,X1 + X2,X1 + X2 + X3.

我已经为你的例子中的n = 4情况说明了这一点,但我希望你可以从中找出一般n的答案.