前缀和+贪心

lc517

先判断衣物总数能否均分

通过前缀和计算衣物转移的累积流量

取“单台机器超量数”和“累积流量绝对值”的最大值，得到最少操作步数

为什么 machines[i] - avg 不用取绝对值呢

• 一个洗衣机一次最多只能移出去一件衣服，但可能接收多件衣服

class Solution {

typedef long long ll;

public:

int findMinMoves(vector<int>& machines) {

ll sum = 0;

for (auto& m : machines) sum += m;

int n = machines.size();

if (sum % n != 0) return -1;

int avg = sum / n;

int ret = 0;

ll pre_sum = 0; // 前缀和，记录当前位置前的衣物总量差

for (int i = 0; i < n; ++i) {

pre_sum += machines[i] - avg;

// 取三个值的最大值：当前机器需移出的衣物数、前缀和绝对值、当前结果

ret = max({ret, machines[i] - avg,abs((int)pre_sum)});

}

return ret;

}

};