Leetcode517 超级洗衣机
题目描述
假设有 台超级洗衣机放在同一排上。开始的时候，每台洗衣机内可能有一定量的衣服，也可能是空的。
在每一步操作中，你可以选择任意 台洗衣机，与此同时将每台洗衣机的一件衣服送到相邻的一台洗衣机。
给定一个非负整数数组代表从左至右每台洗衣机中的衣物数量，请给出能让所有洗衣机中剩下的衣物的数量相等的最少的操作步数。如果不能使每台洗衣机中衣物的数量相等，则返回 -1。
示例
示例1
输入: [1,0,5]
输出: 3
解释:
第一步: 1 0 5 => 1 1 4
第二步: 1 1 4 => 2 1 3
第三步: 2 1 3 => 2 2 2
示例2
输入: [0,3,0]
输出: 2
解释:
第一步: 0 3 0 => 1 2 0
第二步: 1 2 0 => 1 1 1
题目分析
这道题要我说的话，有一点点水往低处流的感觉。比如示例1可以用下面这张图表示。
想起来有点复杂，所以我们先考简单的步骤，什么时候返回-1。
显而易见，在这道题目中如果衣服的总数无法被洗衣机平均就返回-1。
所以我们可以先写下如下代码，解决一下简单的情况。
int findMinMoves(vector<int>& machines) {
int sum = 0;
for (auto i : machines)
sum += i;
int ret = -1;
if (sum % machines.size() == 0){
}
return ret;
} 接下来我们要挽起袖子解决主要问题了。
就以刚刚的图为例，我们的初始状态是，末状态为
。
第一台洗衣机的数量从1变成了2，很自然的一个问题是，他的衣服是从哪里来的。
废话，当然是右边的洗衣机给他的。
所以我们从左往右思考，1号洗衣机缺一件衣服，所以它肯定是从2号洗衣机那里拿了一件衣服。
一号的情况分析清楚了，我们再来看2号洗衣机，2号洗衣机的初始状态为1，末状态为2。但除了自身需要的两件衣服以外，2号洗衣机还需要给1号洗衣机1件衣服。所以2号洗衣机给了1号洗衣机一件衣服，向3号洗衣机要了3件衣服。
同理可得，3号洗衣机给了2号洗衣机3件衣服。
写成表格的话就是这样。
| | 1号 | 2号 | 3号 |
| ---- | ---- | ---- | ---- |
| L | 0 | +1 | +3 |
| R | -1 | -3 | 0 |
L代表应该给左边的衣服件数， R代表应该给右边的衣服件。很容易发现的事实是。
事情是理清楚了，但是我们要求的是最少的移动次数，这和洗衣机之间的“债务”有什么关系呢？
事实上，这道题目的答案就是
根据贪心的思想，每件衣服一旦出发之后，就马上往目的地走一刻也不停留，先出发的衣服会被派到更远的地方去，而不是中途逗留。
比如在上面的例子中3号洗衣机送出去的第1件衣服是到了1号洗衣机的，而不是停留在2号洗衣机。因为让先出发的衣服去最远的目的地，才能最大程度节省时间。
一个直观的理解是，如果每台洗衣机都把自己多的衣服送出去了，那么衣服就已经平均分好了。
你可能要问，有没有可能，3号已经把衣服送过去了，但2号和1号还没有收拾好呢？
答案是不可能，因为先出发走的远的原则，我们知道，
每台洗衣机送出去的最后一件衣服肯定是直接给自己的邻居用的,不存在
到
再到
，的情况，2号洗衣机应该直接给1号洗衣机送衣服。
每件衣服到达目的地时，在这件衣服之前出发的衣服一定已经到目的地了。
时间出发的衣服目的地最多比
出发的衣服远一个单位，但
根据这两条性质，我们知道，当最后一件衣服送出去的时候，所有的衣服已经"归位"了。
而整个过程需要的时间，就是
如果和
一正一负，那就是取大的，如果两者都是正数，那就说明这台洗衣机要同时给两边送衣服，一次只能送一件，所以是
。
最后补全代码就是这样
int findMinMoves(vector<int>& machines) {
int sum = 0;
for (auto i : machines)
sum += i;
int ret = -1;
if (sum % machines.size() == 0){
int p = sum/machines.size();
int l = 0, r = 0;
for (int i = 2; i < machines.size(); i++){
r = r + machines[i] - p;
ret = max(ret, max(l, max(r, l+r)));
l = -r;
}
}
return ret;
}
京公网安备 11010502036488号