517. 超級洗衣機

假設有 n 臺超級洗衣機放在同一排上。開始的時候，每臺洗衣機內可能有一定量的衣服，也可能是空的。

在每一步操作中，你可以選擇任意 m (1 <= m <= n) 臺洗衣機，與此同時將每臺洗衣機的一件衣服送到相鄰的一臺洗衣機。

給定一個整數數組 machines 代表從左至右每臺洗衣機中的衣物數量，請給出能讓所有洗衣機中剩下的衣物的數量相等的 最少的操作步數 。如果不能使每臺洗衣機中衣物的數量相等，則返回 -1 。

示例 1：輸入：machines = [1,0,5]
輸出：3
解釋：
第一步:    1     0 <-- 5    =>    1     1     4
第二步:    1 <-- 1 <-- 4    =>    2     1     3    
第三步:    2     1 <-- 3    =>    2     2     2   
示例 2：輸入：machines = [0,3,0]
輸出：2
解釋：
第一步:    0 <-- 3     0    =>    1     2     0    
第二步:    1     2 --> 0    =>    1     1     1     
示例 3：輸入：machines = [0,2,0]
輸出：-1
解釋：
不可能讓所有三個洗衣機同時剩下相同數量的衣物。

解題思路

1. 先計算出衣服的總數，判斷衣服能否被平均分到每一臺洗衣機里面
2. 對于每一臺洗衣機，我們可以計算出其與平均后衣服數量的差值，如果為負數，意味著需要抽調其他洗衣機的衣服過來，如果為正數，則是需要把當前衣服移除出去。我們將前面若干洗衣機分為一組，后面分為一組，維護一個變量sum，代表前一組洗衣機需要移動多少件衣服進入后一組才可以使得衣服的數量均等。因為每次只能移動一件衣服，因此如果要把前一組的移動到后一組來補充衣服的話，最少需要sum次移動，特殊情況是，當其他一個洗衣機衣服太多，不光要分去后一組，還要平攤到前一組的前部分，至少需要machines[i]-tar次移動

代碼

class Solution {public int findMinMoves(int[] machines) {int n=machines.length,sum=0;for(int m:machines)sum+=m;if(sum%n!=0) return -1;int tar=sum/n,pre=0,res=0;for(int i=0;i<n;i++){machines[i]-=tar;pre+=machines[i];res=Math.max(res,Math.max(Math.abs(pre),machines[i]));} return res;}
}