[LeetCode] 517. Super Washing Machines

https://leetcode.com/contest/leetcode-weekly-contest-20/problems/super-washing-machines/

Solution:
To be honest, I don't exactly know how to solve this problem... Anyway, here I just post one answer that I obtained from the online contest submission from this author:
https://leetcode.com/tckwok0/

This solution looks like using idea of graph theory. When the number of the clothes is less than the average, (average-v[i]) clothes needs to be moved in; in the opposite, (v[i]-average) clothes needs to be moved out. If average == v[i], no net flux is needed.

If we scan the vector from the left to right, we can find the local flux needed to balance them. Since for every move, we can only adjust one clothes, the value of flux actually is the minimum number of move needed. The maximum of the local flux actually is then the minimum moves needed to guarantee the balancing of the whole vectors, which is the answer to this question.

Further thing: can we figure out each step of moving for the minimum move?

Code:

class Solution {
public:
    int findMinMoves(vector<int>& machines) {
        int res = 0, n = machines.size(), sum = 0;
        for(auto a:machines) sum += a;
        if(sum%n) return -1;
        int ave = sum/n, s = 0;
        vector<int> outdegree(n, 0);
        for(int i=0; i<n; ++i){
            s += machines[i] - ave;
            if(s<0) {
                outdegree[i+1] -= s; 
                res = max(res, outdegree[i+1]);
            }
            else if(s>0) {
                outdegree[i] += s;
                res = max(res, outdegree[i]);
            }
        }
        return res;
    }
};