[刷题防痴呆] 0517 - 超级洗衣机 (Super Wash

题目地址

https://leetcode.com/problems/super-washing-machines/

题目描述

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 machines representing the number of dresses in each washing machine from left to right on the line, return 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.

 

Example 1:

Input: machines = [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
Example 2:

Input: machines = [0,3,0]
Output: 2
Explanation:
1st move:    0 <-- 3     0    =>    1     2     0
2nd move:    1     2 --> 0    =>    1     1     1
Example 3:

Input: machines = [0,2,0]
Output: -1
Explanation:
It's impossible to make all three washing machines have the same number of dresses.

思路

• 贪心.
• 如果total可以被洗衣机的个数整除, 肯定有解. 否则返回-1.
• 算平均值.
• 对于每一位, 要求出当前位置与平均值的差值, 和之前流剩下的sum.
• 这中间最大的就是对于该位想要到达平均所需要的值.
• 对每一位求max即可.

关键点

代码

• 语言支持：Java

class Solution {
    public int findMinMoves(int[] machines) {
        int total = 0;
        for (int num: machines) {
            total += num;
        }
        int n = machines.length;
        if (total % n != 0) {
            return -1;
        }

        int average = total / n;
        int res = 0;
        int sum = 0;
        for (int num: machines) {
            num -= average;
            sum += num;
            res = Math.max(res, Math.max(Math.abs(sum), num));
        }

        return res;
    }
}