重新平衡衣物的最少轮次

Question

我正在为下面的洗衣任务寻找线性时间算法。

一家洗衣店有N台机器。他们有无限的能力。现在，一卡车的布料被卸下来进行清洗，并随机分配到每台机器上。在此过程中，经理未能平衡要清洁的布的负载。现在需要重新平衡。

再平衡分轮进行。每次一台机器最多可以将一块布传送给它的每个邻居。机器 i 的邻居是机器 i-1 和 i+1（机器 1 和 N 各只有一个邻居，分别为 2 和 N-1）。再平衡的目标是实现所有机器拥有相同数量的布料。

给定最初分配给每台机器的布料数量，要求您确定当每台机器具有相同数量的布料时达到该状态所需的最小轮数，或者确定这种重新平衡是不可能的。

Answer 1

设 C 为布料总数。当且仅当 N 整除 C 时，才有解。

在这样的解决方案中，每台机器都有精确的C/N布料。令 c_i 为机器 i 最初持有的布料数量。定义机器 i 的剩余为 s_i = c_i - C/N。请注意，盈余可能为负数；这在英语中通常称为“赤字”。 定义 f_{i,i+1} = sum_{j≤i} s_i 并考虑机器 i 和 i+1 进行的交换。从 i 发送到 i+1 的衣服数量减去从 i+1 发送到 i 的衣服数量必须等于 f_{i,i+1}，这可以通过考虑 1..i 中的衣服数量来看出时间。

声明：最优解所走的圈数为T = max_i |f_{i,i+1}|。显然这个运行时间是必要的，因为 |f_{i,i+1}|每回合最多减少一个。充分性的证明是通过对 T 进行归纳。基本情况是当 T = 0 时。然后所有 f 也都为零，我们已经完成了。否则，每台机器 i 使得 f_{i,i+1} = T 应该向 i+1 发送一块布料，并且每台机器 i+1 使得 f_{i,i+1} = -T 应该向 i+1 发送一块布料我。这些机器至少有一块布，因为流量表明它们发出的多于吸收的，并且新配置将 T 减少了 1。

Answer 2

Answer 3

方便：当您选择班加罗尔最好的洗衣服务时，您就可以让我们帮您洗衣服，从而腾出您的日程安排。这可以让您享受更多的个人时间或专注于其他责任。
质量：由于我们使用高品质的洗涤剂和先进的洗涤技术，FaabroCare 成为班加罗尔最好的洗衣清洁服务。与在家清洗相比，您的衣服会更干净、更清新、更好护理。
效率：凭借我们专业的设备和技术精湛的团队，班加罗尔最好的洗衣清洁服务确保您的洗衣快速高效地完成，减少等待衣服晾干的麻烦。
成本效益：虽然有些人可能会看到专业洗衣服务的价格标签，但节省时间、精力和衣服寿命使班加罗尔最好的洗衣清洁服务成为一项有价值的投资。
如果您想要卓越的服务和便利，FaabroCare 提供班加罗尔最好的洗衣服务。

访问我们的网站：班加罗尔最佳干洗服务和高级洗衣服务|立即预订 - 免费取货和送货（班加罗尔最好的干洗服务和高级洗衣服务 | 立即预订 - 免费取货和送货）或致电：([phone]