leetcode 517. Super Washing Machines 超级洗衣机 + 传递衣服 + 发现规律

本是古典何须时尚 2022-06-03 03:12 126阅读 0赞

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:  
The range of n is \[1, 10000\].  
The range of dresses number in a super washing machine is \[0, 1e5\].

题意很简单，我们就用上面那个例子，有四个洗衣机，装的衣服数为\[0, 0, 11, 5\]，最终的状态会变为\[4, 4, 4, 4\]，那么我们将二者做差，得到\[-4, -4, 7, 1\]，这里负数表示当前洗衣机还需要的衣服数，正数表示当前洗衣机多余的衣服数。我们要做的是要将这个差值数组每一项都变为0，对于第一个洗衣机来说，需要四件衣服可以从第二个洗衣机获得，那么就可以把-4移给二号洗衣机，那么差值数组变为\[0, -8, 7, 1\]，此时二号洗衣机需要八件衣服，那么至少需要移动8次。然后二号洗衣机把这八件衣服从三号洗衣机处获得，那么差值数组变为\[0, 0, -1, 1\]，此时三号洗衣机还缺1件，就从四号洗衣机处获得，此时差值数组成功变为了\[0, 0, 0, 0\]，成功。那么移动的最大次数就是差值数组中出现的绝对值最大的数字，8次，

代码如下：

#include <iostream>
    #include <vector>
    #include <map>
    #include <unordered_map>
    #include <set>
    #include <unordered_set>
    #include <queue>
    #include <stack>
    #include <string>
    #include <climits>
    #include <algorithm>
    #include <sstream>
    #include <functional>
    #include <bitset>
    #include <numeric>
    #include <cmath>
    #include <regex>
    #include <iomanip>
    
    using namespace std;
    
    
    class Solution
    {
    public:
        int findMinMoves(vector<int>& mac) 
        {
            long long sum = accumulate(mac.begin(), mac.end(), 0);
            if (sum % (int)mac.size() != 0)
                return -1;
            int count = 0, aver = sum / mac.size(), balance = 0;
            for (int m : mac)
            {
                balance += m - aver;
                count = max(count, max(abs(balance), m - aver));
            }
            return count;
        }
    };