算法在一个组的成员内完成许多事务至少没有。步骤

Question

假设我们有如下情况:

A has to give $10 to B. 
B has to give $20 to C. 
C has to give $10 to D.

现在这种情况可以简化为:

A loses $10 i.e A=-10
B gains $10 from B but loses $20 to C i.e B=-10
C gains $20 from B but loses $10 to D i.e c=10
D gains $10 i.e D=10

因此，交易可以简化为:A 给 C 10 美元，B 给 D 10 美元。

另一个例子:

A gives $1 to B.
B gives $1 to C.
C gives $1 to D.

这可以简化为:A 给 D 1 美元。

以与上述示例类似的方式，我想编写一个计算机程序来找到完成任何给定交易集的最简单方法。但是我不能为此设置算法。如果有人对此有想法，请帮助我。谢谢。

Answer 1

我可以建议以下算法:

1. 为每个用户分配一个数组，并为他们的交易分配一个数组。示例:用户 = [A,B,C,D]; sum = [0,0,0,0];
2. 用每个事务更新总和数组示例:[-10,10,0,0] -> [-10,-10,20,0] -> [-10,-10,10,10 ]
3. 使用任何复杂度为 O(nlogn) 的算法对数组进行排序。同时更新用户数组。
4. 在总和数组中找到负结和正结(理想情况下，您可以在排序过程中存储它，也可以进行二分查找)。
5. 接下来，将求和数组中的负值分配给正值。示例:在我们的例子中，排序后的总和数组将与原始 [-10,-10,10,10] 相同，正负交界处是总和数组的第二个索引。所以我们开始在一个循环中分配作为 sum[i] 到 sum[2 + i] 并在 sum 中找到多余或不足并在下一次迭代中调整它。