517. 超级洗衣机 力扣(困难) 贪心,不会

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

题解:https://leetcode-cn.com/problems/super-washing-machines/solution/acmjin-pai-ti-jie-tan-xin-bian-cheng-xio-mp7n/

 

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

 

上一篇:贪心算法之多机调度问题


下一篇:LeetCode 517. 超级洗衣机(贪心,不太理解)/ 223. 矩形面积 / 1436. 旅行终点站