文章目录
前言
一、解题思路
代码
前言
假设有 n 台超级洗衣机放在同一排上。开始的时候，每台洗衣机内可能有一定量的衣服，也可能是空的。
在每一步操作中，你可以选择任意 m (1 <= m <= n) 台洗衣机，与此同时将每台洗衣机的一件衣服送到相邻的一台洗衣机。
给定一个整数数组 machines 代表从左至右每台洗衣机中的衣物数量，请给出能让所有洗衣机中剩下的衣物的数量相等的 最少的操作步数 。如果不能使每台洗衣机中衣物的数量相等，则返回 -1 。
来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/super-washing-machines
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
一、解题思路
思想传统:算单点的瓶颈,最后看总答案跟单点瓶颈之间的关系
假设来到某一台(i号)洗衣机 衣服数量?
假设每台机器该有的平均数我们知道
左侧整体欠15件。而它右侧整体多10件,假设位置永远有衣服可以搬，至少要几轮。
至少要15轮
i如果衣服特别少就可能左右两侧都要给它衣服
最少也是需要15轮
如果左侧欠15件。右侧7件，我问你是要搬多少轮,两侧都指望着i出力，它每次只能扔一件。
因此需要22轮
先算一个总衣服的数量，你再算一个左侧部分的累加和, i位置自己有值。
左侧部分欠几件还多几件,右侧部分欠几件还是多几件。都能算出来
有一个衣服的总数量，有一个i左侧的累加和,接下来你到任何一个i位置。
你左侧，右侧到底是多还是少?你都能算出来
根据我们的策略。我们算出零位置时候的瓶颈要多少轮，1位置时候的瓶颈要多少轮,
2位置时候的瓶颈要多少轮,每一个位 置的瓶颈要多论。结论是所有答案中最痛的点求的max,决定了整体的瓶颈。
因为当最痛瓶颈满足的同时，其他的瓶颈同步就解决了
因为每一轮他都可以并行的搬。 所以你最痛的瓶颈决定了一共的轮数。 没有为什么数学证明很麻烦
代码
class Solution {
public int findMinMoves(int[] arr) {
if (arr == null || arr.length == 0) {
return 0;
}
int size=arr.length;
int sum=0;
for(int i=0;i<size;i++){
sum+=arr[i];
}
if(sum%size!=0){
return -1;
}
int avg=sum/size;
int leftSum=0;
int ans=0;
for(int i=0;i<size;i++){
// 左边差的数量
int leftRes=leftSum-i*avg;
// 右边差的数量
int rightRes=(sum-leftSum-arr[i])-(size-i-1)*avg;
if(leftRes<0&&rightRes<0){
ans=Math.max(ans,Math.abs(leftRes)+Math.abs(rightRes));
}else{
ans=Math.max(ans,Math.max(Math.abs(leftRes),Math.abs(rightRes)));
}
leftSum+=arr[i];
}
return ans;
}
}
