Leetcode517 超级洗衣机

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;
}