题目描述
这是 LeetCode 上的「517. 超级洗衣机」，难度为「困难」。
Tag : 「贪心」
假设有 n 台超级洗衣机放在同一排上。开始的时候，每台洗衣机内可能有一定量的衣服，也可能是空的。
在每一步操作中，你可以选择任意 m (1 <= m <= n) 台洗衣机，与此同时将每台洗衣机的一件衣服送到相邻的一台洗衣机。
给定一个整数数组 machines 代表从左至右每台洗衣机中的衣物数量，请给出能让所有洗衣机中剩下的衣物的数量相等的 最少的操作步数 。如果不能使每台洗衣机中衣物的数量相等，则返回 -1 。
示例 1：
代码语言：javascript复制输入：machines = [1,0,5]
输出：3
解释：
第一步: 1 0 <-- 5 => 1 1 4
第二步: 1 <-- 1 <-- 4 => 2 1 3
第三步: 2 1 <-- 3 => 2 2 2
示例 2：
代码语言：javascript复制输入：machines = [0,3,0]
输出：2
解释：
第一步: 0 <-- 3 0 => 1 2 0
第二步: 1 2 --> 0 => 1 1 1
示例 3：
代码语言：javascript复制输入：machines = [0,2,0]
输出：-1
解释：
不可能让所有三个洗衣机同时剩下相同数量的衣物。
提示：
基本分析
由于最终是要让所有洗衣机衣服相等，因此无解的情况很好分析，如果衣服数量
不能整除洗衣机数量
的话，则返回
，否则必然有解（最坏情况下，每次只移动一件衣服，也可以使得衣服均分），要求最小移动次数。
由于每次操作都可以选任意台机器进行，不难猜想到最小移动次数为 所有机器的「最小运输衣服数量」中的最大值。
计算某台洗衣机的「最小运输衣服数量」为经过当前机器的衣服数量（每次只能运输一件衣服），其值等于「起始左边衣服总量 与 最终左边衣服总量 的差值」 「起始右边衣服总量 与 最终右边衣服总量 的差值」，这里的差值都需要与
取
代指缺少衣服的数量（因为如果是多余数量的话，可以通过同时传输来满足增加缺少的一边，减少多余的一边）。
我们猜想取所有机器中的「最小操作次数」的最大值即是答案。
但这显然是理论的最小操作次数，我们来证明最终答案等于该值。
假设理论最下操作次数为
，真实答案为
，那么天然有
，我们需要通过证明
恒成立，来得证
。
可以通过「反证法」来证明
恒成立，假设
，即在某个特定序列中，实际最小操作次数
大于
，假定我们是在位置
中取得这个实际最小操作次数。
那么我们需要思考：在没有无效传输的前提，什么情况下需要在
位置传输大于
件衣服来达到最终平衡。
❝注：无效的意思是，衣服从位置
的一边传到另外一边，随后又传输回来。 ❞
（注 1）当且仅当位置
本身衣服为
时，会发生该种情况。
也就是说首次传输，并没有实现「从
左边往右边传输衣服」或者「从
右边往左边传输衣服」的目的，而是需要先往位置
填送衣服。
那么是否可能由起始衣服为
的位置来取得
呢？我们通过「反证法」来证明「
不可能由衣服为
的起始位置得出」。
由于位置
的起始数量为
，那么位置
必然至少有一侧的起始数量小于最终数量的（缺少衣服的），可以继续利用「反证法」来证明：
- 如果是两边都多于最终数量，说明最终是两边衣服流向位置
，而且我们得到的
是两边的缺少总和，这种情况下得到的
为
，但是整体衣服本身不相等，必然要消耗步数，必然不为
，因此该情况不存在。
既然位置
至少有一侧的起始数量小于最终数量的（缺少衣服的），那么自然我们可以将位置
归到那一边，使得那一侧缺少衣服的数量更多，从而使答案
更大。这与
为所有位置中的「最小操作次数」最大的位置矛盾。
得证，取得
的位置
起始衣服必然不为
。
如果位置
起始衣服必然不为
，那么（注 1）的条件不成立，则
恒不成立，得证
恒成立。
至此，我们通过三次「反证法」来证明了结论成立。首先通过「反证法」证明取得
的位置
衣服不可能为
；然后根据该位置起始衣服不为
的前提条件，来证明
恒不成立，得证
恒成立，最终结合
来得证
。
贪心
实现上，首先我们可以求得衣服总和
以及洗衣机数量
，从而判断无解情况（sum % n != 0），或者计算最终每台洗衣机的衣服数量
。
然后使用两个变量
和
分别表示当前位置「左边的衣服总数」和「右边的衣服总数」，并在从左往右的遍历过程中实时维护。
对于某个位置
而言，达到最终平衡需要从
右边往左边运送的衣服数量为
，即左边的当前的衣服数量与最终状态的衣服数量的差值，与
取
含义代表为如果当前左边衣服多于最终衣服数量时，此时不需要消耗从右到左的移动次数（只需要消耗从
左边到
右边的移动次数）；右边分析同理，我们可以得到达到最终平衡需要从
左边到右运送的衣服数量为
。
在所有位置的
之间取最大值即是答案。
代码：
代码语言：javascript复制class Solution {
public int findMinMoves(int[] ms) {
int n = ms.length;
int sum = 0;
for (int i : ms) sum = i;
if (sum % n != 0) return -1;
int t = sum / n;
int ls = 0, rs = sum;
int ans = 0;
for (int i = 0; i < n; i ) {
rs -= ms[i];
int a = Math.max(t * i - ls, 0);
int b = Math.max((n - i - 1) * t - rs, 0);
ans = Math.max(ans, a b);
ls = ms[i];
}
return ans;
}
}
- 时间复杂度：
- 空间复杂度：
最后
这是我们「刷穿 LeetCode」系列文章的第 No.517 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，部分是有锁题，我们将先把所有不带锁的题目刷完。
在这个系列文章里面，除了讲解解题思路以外，还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。
为了方便各位同学能够电脑上进行调试和提交代码，我建立了相关的仓库：https://github.com/SharingSource/LogicStack-LeetCode 。
在仓库地址里，你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。
