最小化分配在糖果圈中的步驟

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並且恰好是-ve的一半，因爲如果不是這種情況，我們可以增加或減少k以使事情更好 - k值的選擇是 - 0，X1，X1 + X2，X1 + X2 + X3的中位數。

我已經對你的例子中n = 4的情況說明了這一點，但是我希望你能從中得出一般n的答案。

Answer 2

這裏應用的一個元方法是採用輪詢並使其基於事件的算法。我是什麼意思？

保持一個包含送禮者（兒童> 0個糖果）和接受者（兒童與糖果< 0）的循環鏈表。維護一個優先級隊列，其中包含每個相鄰（在列表中，而不是在圓圈內）給予者對的條目，其關鍵是給予者和接受者之間的距離。

現在，不是一次遞增一個距離，而是使用優先級隊列來確定發生的下一個有趣事情。每當一對接受者獲得解決時，一個或兩個孩子就會從列表中退出，這需要O（1）簿記和隊列插入。

Answer 3

以mcdowella的想法，並把它變成我的話（因爲我花了一段時間來理解它，看到here一些大聲疾呼關於這一主題），使得它看起來如下。關鍵的見解是：

• 就像你可以根據自己的消極糖果，你可以通過負糖果以及
• 傳遞負糖果在一個方向基本上是通過（正）糖果相反的方向
• 不管每個孩子都有的糖果，每個人都會以零爲結果。

這實現這一如下：選擇一個任意的孩子開始（如下圖，在那裏我有5個孩子，而不是4兒童A），我們選擇一個任意的方向（逆時針方向，在我們的例子） ，並開始傳球。每個孩子必須擺脫所有的糖果（正面或負面）才能達到零。所以孩子A有-2糖果，所以我們把它傳遞給孩子B.之後，孩子B有-5糖果，所以我們把它傳遞給孩子C.現在孩子C有-4糖果，並將其傳遞給D，等等。這是第二張圖，所有糖果在13次移動中都爲零。

的SENTER圖不是最佳的。我們觀察到，這是一個在中心圖通過了所有的糖果是負的（保存E->一通）和我們可以隨意添加或第一遍減去：如果A-> B傳球被+5而不是-2，那麼所有通行證將增加7，並且E-> A通行證將是7而不是0，並且最後A將仍然沒有糖果。所以我們尋找一個數字，我們可以調整所有通道，使所有通道的絕對值之和最小化。在上圖中我們看到，如果我們將+2添加到所有通行證中，則所有通行證的絕對值總和爲7.作爲說明，如果我們添加了+3，則總和會更大。所以我們試圖給所有通道添加一個常數，使所有通道的絕對值之和最小。

P.S.如果有人認爲我不應該在這裏重複講述mcdowella的想法，我會很樂意刪除。