找到相鄰硬幣移動的最小數量？

Question

給出一堆硬幣（例如5堆：9,0,5,1,5）共20個硬幣。所需的動作，以便所有的樁都有相同數量的硬幣（4,4,4,4,4）（這是9次移動）規則：一枚硬幣可以移動到只有相鄰的樁..即。如果第j個堆硬幣存在，它可以移動到j-1或j + 1。

解決謎題的任何好算法？

Answer 1

所有堆的大小的算術平均值爲您提供了每根樁的所需尺寸，讓它爲d，而樁數n。我們首先假設在構建解決方案時，我們有時可能會有一堆負面的大小，我們會立即修復這個假設。 O（n）算法如下 - 讓我們看看第一堆。如果尺寸爲d，那麼我們既不想改變它的尺寸，也不想將硬幣通過其他樁，因爲左側沒有樁。這意味着最佳解決方案不會改變這一堆的尺寸，我們可以忘掉它。但是，如果第一堆的尺寸是d'> d，那麼我們知道我們想從中移除（d' - d）個硬幣。因爲他們只能走一條路 - 正確的做法是，我們可以做到這一點，將第一個堆放到d，然後像以前一樣忘掉它。同樣，如果d'< d，那麼在某個時間點，我們將不得不從第二堆中取出一些硬幣，所以我們這樣做，並忘記第一堆。

因爲我們忘了第一堆，我們可以想象，我們刪除了它，第二個現在是第一個。我們通過所有的樁繼續這個過程，當移動一些硬幣時，我們將這些移動添加到某個櫃檯。

還有一個問題 - 負樁。讓我們列舉我們在解決方案中執行的所有操作，很容易看出我們執行的順序並不重要。我們可以做出非法行爲的唯一動作是那些當我們從堆（i + 1）中拿走硬幣來堆積我，並且可能已經離開（i + 1）負面的情況。這意味着後來我們從（i + 2）到（i + 1）拿了一些硬幣來補償它，如果這個移動是在移動從（i + 1）開始之前完成的，那麼（i + 1）的大小永遠不會是負面的。所以如果我們將從最右邊的一個開始執行預定的移動，那麼一切都會很好 - 這證明構建的解決方案是有效的。