题目描述：

LeetCode 517. Super Washing Machines

You have n super washing machines on a line. Initially, each washing machine has some dresses or is empty.

For each move, you could choose any m (1 ≤ m ≤ n) washing machines, and pass one dress of each washing machine to one of its adjacent washing machines at the same time .

Given an integer array representing the number of dresses in each washing machine from left to right on the line, you should find the minimum number of moves to make all the washing machines have the same number of dresses. If it is not possible to do it, return -1.

Example1

Input: [1,0,5]

Output: 3

Explanation: 
1st move:    1     0 <-- 5    =>    1     1     4
2nd move:    1 <-- 1 <-- 4    =>    2     1     3    
3rd move:    2     1 <-- 3    =>    2     2     2   

Example2

Input: [0,3,0]

Output: 2

Explanation: 
1st move:    0 <-- 3     0    =>    1     2     0    
2nd move:    1     2 --> 0    =>    1     1     1     

Example3

Input: [0,2,0]

Output: -1

Explanation: 
It's impossible to make all the three washing machines have the same number of dresses. 

Note:

1. The range of n is [1, 10000].
2. The range of dresses number in a super washing machine is [0, 1e5].

题目大意：

给定一个长度为n的整数数组nums，每一次选择m个数(1 ≤ m ≤ n)进行移动：将这m个数-1，同时令其相邻元素+1（这m个数同时可以是被加元素）

求最少需要多少次移动，使得nums的所有元素均相等。如果不能，则返回-1。

解题思路：

下列解法均摘自LeetCode Discuss，暂时无法证明解法的正确性

解法I 参考：https://discuss.leetcode.com/topic/79938/very-short-easy-java-o-n-solution

Python代码：

class Solution(object):
    def findMinMoves(self, machines):
        """
        :type machines: List[int]
        :rtype: int
        """
        if sum(machines) % len(machines):
            return -1
        avg = sum(machines) / len(machines)
        ans = total = 0
        for m in machines:
            total += m - avg
            ans = max(ans, abs(total), m - avg)
        return ans

解法II 参考：https://discuss.leetcode.com/topic/79923/c-16ms-o-n-solution

Python代码：

class Solution(object):
    def findMinMoves(self, machines):
        """
        :type machines: List[int]
        :rtype: int
        """
        total = sum(machines)
        size = len(machines)
        if total % size:
            return -1
        avg = total / size
        sums = [0] * size
        last = 0
        for i, m in enumerate(machines):
            last += m
            sums[i] = last
        ans = 0
        for i, m in enumerate(sums):
            left = i * avg - m + machines[i]
            right = (size - i - 1) * avg - sums[size - 1] + m
            if left > 0 and right > 0:
                ans = max(ans, left + right)
            else:
                ans = max(ans, abs(left), abs(right))
        return ans

 

本文链接：http://bookshadow.com/weblog/2017/02/19/leetcode-super-washing-machines/
请尊重作者的劳动成果，转载请注明出处！书影博客保留对文章的所有权利。

如果您喜欢这篇博文，欢迎您捐赠书影博客： ，查看支付宝二维码