LeetCode 517. 超级洗衣机
题目描述
题意分析
每轮可以同时选择多台洗衣机，让每台选中的机器向一个相邻机器送出一件衣服。一台每轮最多送一件，但可以同时从两侧接收。求各机器最终衣服数相等的最少轮数；总数不能被机器数整除时返回
-1。
解法：前缀净流量 + 并行瓶颈
核心思路
[!blue]
总衣服数不会变化，所以先求目标平均数
avg，不能整除就无解。令diff = machines[i] - avg表示当前机器自身的盈亏，令balance表示扫描到当前机器为止的前缀总盈亏。前缀最终也必须恰好拥有对应数量的衣服，它与剩余机器之间只有一条相邻分界。因此
balance > 0时必须有这么多件衣服净流向右边，balance < 0时必须从右边净流入。每轮沿规定方向最多通过一件，故至少需要abs(balance)轮。这条流量由前缀总量唯一确定，与具体如何安排无关。还要考虑一台机器同时补给两侧的情况。它每轮只能送出一件，自身多出的正
diff件至少需要diff轮送走。负diff只是接收需求，一台可以同时从两侧接收，不能把abs(diff)也当作单机轮数下界。这两类量已经覆盖全部送出负载。设当前机器左侧分界的前缀盈亏为
before，右侧为balance，它向左需送max(-before, 0)件，向右需送max(balance, 0)件。若两侧都要送，总量恰好是balance - before = diff；若只向一侧送，总量就是那一侧的分界流量。因此所有机器所需送出次数的最大值，正是所有abs(balance)与正diff的最大值。这些负载可以并行完成，无需把衣服经过的所有边相加。沿每条分界只安排必要的净方向，向两侧送出的机器没有外部补给依赖，原有衣服已经足够；只负责接收的机器也不占用送出轮次。中转机器则可以每轮送出已有的一件，同时接收上游的一件。若存在衣服需要移动，整数平均数至少为一；中转机最终要保留衣服，因此最后一轮收到的一件可以直接留下，不必再增加一轮转发。沿这些有向路段持续传送，就能在最大送出负载限定的轮数内完成，使上述下界可以达到。
因而只需线性扫描，持续更新
answer = max(answer, abs(balance), diff)。已经均衡或全部为零时，所有负载均为零，答案也自然为零。
解题步骤
- 计算总数，若不能被机器数量整除，返回
-1。- 计算
avg，初始化balance = 0、answer = 0。- 对每台机器求
diff，将它累加到balance，得到当前右侧分界的净流量。- 用分界流量绝对值和单机盈余更新答案，遍历结束后返回最大瓶颈。
代码实现
class Solution {
public int findMinMoves(int[] machines) {
int n = machines.length;
int sum = 0;
for (int x : machines) {
sum += x;
}
if (sum % n != 0) {
return -1;
}
int avg = sum / n;
int answer = 0;
int balance = 0;
for (int x : machines) {
int diff = x - avg;
// 前缀盈亏决定这条相邻分界必须通过的净衣物数量。
balance += diff;
// 跨边流量看绝对值，单机瓶颈只看需要送出的正盈余。
answer = Math.max(answer, Math.max(Math.abs(balance), diff));
}
return answer;
}
}
func findMinMoves(machines []int) int {
n := len(machines)
sum := 0
for _, x := range machines {
sum += x
}
if sum%n != 0 {
return -1
}
avg := sum / n
answer := 0
balance := 0
for _, x := range machines {
diff := x - avg
// 前缀盈亏决定这条相邻分界必须通过的净衣物数量。
balance += diff
// 跨边流量看绝对值，单机瓶颈只看需要送出的正盈余。
answer = max(answer, max(abs(balance), diff))
}
return answer
}
func abs(x int) int {
if x < 0 {
return -x
}
return x
}
func max(a, b int) int {
if a > b {
return a
}
return b
}
复杂度分析
- 时间复杂度：$O(n)$，先统计总数，再扫描前缀盈亏。
- 空间复杂度：$O(1)$，只保存总数、平均数、前缀盈亏与答案。
关键点总结
[!green]
- 前缀盈亏确定每条分界必须通过的净流量。
- 跨边流量限制持续轮数，双向送出的正盈余限制单机总工作量。
- 多台可以同时工作，所以取最大负载，而非累计所有移动次数。
易错点总结
[!yellow]
- 总数不能整除时没有合法平均数，不能继续按向下取整的结果计算。
- 只看分界流量，会遗漏一台必须分两边送出的总次数；只看单机盈余，又会遗漏中转经过的衣服。
- 负盈亏不应取绝对值作为单机下界，接收并不受“每轮最多送一件”的约束。
- 同轮接收与送出可以并行，但不能理解为一件刚到达的衣服在同一轮跨越多台机器。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 979. 在二叉树中分配硬币 | 中等 | 同样通过子结构的净盈亏推导必须经过边的流量，原题统计总移动次数，本题还受同时传递的轮次瓶颈限制。 |