1.题目基本信息

1.1.题目描述

假设有 n 台超级洗衣机放在同一排上。开始的时候，每台洗衣机内可能有一定量的衣服，也可能是空的。

在每一步操作中，你可以选择任意 m (1 <= m <= n) 台洗衣机，与此同时将每台洗衣机的一件衣服送到相邻的一台洗衣机。

给定一个整数数组 machines 代表从左至右每台洗衣机中的衣物数量，请给出能让所有洗衣机中剩下的衣物的数量相等的 最少的操作步数 。如果不能使每台洗衣机中衣物的数量相等，则返回 -1 。

1.2.题目地址

https://leetcode.cn/problems/super-washing-machines/description/

2.解题方法

2.1.解题思路

贪心

2.2.解题步骤

第一步，判断是否有解。根据总和是否能被n整除

第二步，构建维护变量。使用sum2维护sum(machines[i] for i in range(j))-avg*j；结果变量result=max(max(abs(sum2_i),machines[i]-avg) for i in range(n))

3.解题代码

python代码

class Solution:
    def findMinMoves(self, machines: List[int]) -> int:
        # 思路：贪心
        # 第一步，判断是否有解。根据总和是否能被n整除
        n = len(machines)
        sum1 = sum(machines)
        if sum1 % n != 0:
            return -1
        avg = sum1 // n
        # 第二步，构建维护变量。使用sum2维护sum(machines[i] for i in range(j))-avg*j；结果变量result=max(max(abs(sum2_i),machines[i]-avg) for i in range(n))
        sum2 = 0
        result = 0
        for i in range(n):
            sum2 += machines[i] - avg
            result = max(result, abs(sum2), machines[i] - avg)
        return result

c++代码

class Solution {
public:
    int findMinMoves(vector<int>& machines) {
        int n = machines.size();
        int sum1 = 0;
        for (int i = 0; i < n; i++) {
            sum1 += machines[i];
        }
        if (sum1 % n != 0) {
            return -1;
        }
        int avg = sum1 / n;
        int result = 0;
        int sum2 = 0;
        int a;
        for (int i = 0; i < n; i++) {
            a = machines[i] - avg;
            sum2 += a;
            result = max(result, max(abs(sum2), a));
        }
        return result;
    }
};

4.执行结果