No.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
解释：
不可能让所有三个洗衣机同时剩下相同数量的衣物。

 

提示：

  • n == machines.length
  • 1 <= n <= 104
  • 0 <= machines[i] <= 105

思路分析

本题主要的思路就是遍历。 先遍历一遍，求得是否有可行解以及每个位置上的平均衣服的件数avg是多少。 这里肯定大家都想得到。那么下面怎么办呢？ 我们知道，如果衣服多，假设一个位置上有K件衣服，而K>avg,那么我们最终的答案一定不会小于K-avg，因为对于该堆衣服来说，不考虑其他洗衣机的操作，仅对于本洗衣机而言，一定要花费K-avg的时间将里面多出来的衣服分出去。

对于本题我们还知道，可以在遍历数组的时候维护一个cur。假设有一只无形的大手在遍历数组的同时将所有洗衣机里衣服的数量变成了avg，多余的衣服就认为是余量，缺少的就认为是缺口。这样有一个好处，就是能够各司其职。下面的例子能够加强理解。

示例：          [5, 0, 7], avg = 12 / 3 = 4
在遍历时的`cur`值：[1, -3, 0]

这样可以发现，对于本数组而言，cur的最大绝对值就是需要的总时间。因为我们如果单看一个1号位，也就是中间的那一位，我们会发现，一定要4次填充才能将其填到avg。但是这四次填充有一次是来自左边，三次是来自右边，这两段时间是可以重叠的。而cur值就很好的对于缺口和余量的体现。当遍历到这一位，缺口是k时，说明之前的所有洗衣机就算内部匀一匀也还缺k个，必须从cur的右方去移动过来，这个k就是最小移动时间。而当余量是k时，也是一样的道理，说明在cur及cur的左边怎么匀都会多出来k个，必须转移到cur的右边，而转移必须通过cur，也就是说这k个转移是没有叠加的余地的，必须在最短为k的时间内完成。

所以cur可以作为一个全局的转移次数的把控。但还存在一些局限。看下面一个例子

示例：          [0, 3, 0], avg = 3 / 3 = 1
在遍历时的`cur`值：[-1, 1, 0]

这个示例来看，cur忽略了一个非常关键的点，也就是对于3而言，必须花费2次的时间才能将其完全转移出去。但对于cur来说，它并不知道自己所遍历到的-1和1是没法叠加的，都是从3上面分出来的。那么这时候就需要同考虑cur和K-avg对于最终结果的作用了。

Rust代码


#![allow(unused)]
fn main() {
struct Solution;
impl Solution {
    pub fn find_min_moves(machines: Vec<i32>) -> i32 {
        let sum: i32 = machines.iter().sum();
        let n = machines.len() as i32;
        if sum % n != 0 {
            return -1;
        } 
        let avg = sum / n;
        let mut res = 0;
        let mut cur = 0;
        for mut m in machines {
            m -= avg;
            cur += m;
            res = res.max(cur.abs()).max(m);
        }
        res
    }
}
}

C++代码

class Solution {
public:
    int findMinMoves(vector<int>& m) {
        int n = m.size();
        int sum = 0;
        for (auto & t : m) sum += t;
        if (sum % n != 0) return -1;
        int per = sum / n;
        sum = 0;
        int res = 0;
        for (auto & t : m) {
            t -= per;
            sum += t;
            res = max(res, abs(sum));
            res = max(res, t);
        }
        return res;
    }
};