アルゴリズム練習ノート(十二)——スーパー洗濯機

https://leetcode.com/problems/super-washing-machines/#/description
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 theminimum 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     1     1     4
2nd move:    1     2     1     3    
3rd move:    2     1     2     2     2   

Example2

Input: [0,3,0]

Output: 2

Explanation: 
1st move:    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].

n台の洗濯機があると仮定して、すべての洗濯機の中の服の数量はすべて非負で(くだらない話==)、今服を移動して1台の洗濯機の中の服の数量を同じにして、毎回同時に異なる洗濯機の1件の服を移動することができて、服を移動させる最小の歩数を求めます
思考を解く:
最初は、私が同時にこの言葉を見ていないことを許して、そこで悲劇が発生して、私は異なる動的な計画の解答を得て、しかし同時に要求と一致しません
私は最後から洗濯機を巡って、それから毎回、最後の洗濯機の中の服の数を最小ステップ数で移動して必要な数に変えて、それからこの洗濯機を容器から投げ出して、次のステップを行って、少し欲張りなアルゴリズムの感じがします
私の努力した心を慰めるために、私はやはり自分の誤った解答を放します
(異なる場合)

class Solution {
public:
    int findMinMoves(vector& machines) {
        int size = machines.size();
        int count = 0;
        for(int i = 0; i < size; i++){
            count += machines[i];
        }
        if(count%size != 0)return -1;
        else
        return MinMoves(machines, count / size);
    }
    
    int MinMoves(vector& mac, int key){
        int move = 0;
        int size = mac.size();
        if(size == 1)return 0;
        if(mac[size - 1] == key);
        else if(mac[size - 1] > key){
            move = mac[size - 1] - key;
            mac[size - 2] += move;
        }
        else if(mac[size - 1] < key){
            int nums = key - mac[size - 1];
            for(int i = size - 2; i >= 0; i --){
                if(mac[i] > 0 && mac[i] < nums){
                    move += mac[i] * (size - 1 - i);
                    nums -= mac[i];
                    mac[i] = 0;
                }
                else if(mac[i] > 0 && mac[i] >= nums){
                    move += nums * (size - 1 - i);
                    mac[i] -= nums;
                    break;
                }
            }
        }
        mac.pop_back();
        return move + MinMoves(mac, key);
    }

};

そして正解といえばdalaoの解答を参考にして、しかも8行しか使いませんでした!
この解答では、主に今回の情景を分析し、バランスパラメータを作成して同時に問題を解決した.洗濯機ごとに不足した数の服と多く出た服が移動されるため、全体的なバランス量を設定し、洗濯機ごとに移動する必要がある服をカウントし、同時に2つの服を同時に移動できる問題を加算し、解決する.次のようになります.

int findMinMoves(vector& machines) {
    int totalDresses = 0, size = machines.size();
    for (auto i = 0; i < size; ++i) totalDresses += machines[i];
    if (totalDresses % size != 0) return -1;
    
    auto targetDresses = totalDresses / size, totalMoves = 0, ballance = 0;
    for (auto i = 0; i < size; ++i) {
        ballance += machines[i] - targetDresses;
        totalMoves = max(totalMoves, max(machines[i] - targetDresses, abs(ballance)));
    }
    return totalMoves;
}