algo-aha

洗衣机传递衣服

• https://leetcode.com/problems/super-washing-machines/

洗衣机排成一排，每次某些洗衣机向邻居传一件衣服，要几次能使各洗衣机衣服数相等？

int findMinMoves(vector<int>& machines) {
    const int N = machines.size();
    int total = 0;
    for (int machine : machines)
        total += machine;
    if (total % N != 0) return -1;

    // 1. 每个洗衣机要发出衣服：out[i] = machines[i]-avg，
    //    一次只能发一件，需要out[i]次
    // 2. 通过本机向另一侧发送的件数 x = abs( sum(out[0..i] ))，
    //    sum为正向右流、为负向左流，又需要x次
    int avg = total / N;
    int sum = 0;
    int ans = 0;
    for (int i = 0; i < N; i++) {
        int out = machines[i] - avg;
        sum += out; // sum(out[0..i])
        ans = max({ans, out, abs(sum)});
    }
    return ans;
}