现金流问题

假设有一些朋友之间互相具有债务关系，如果已知他们之间的欠款和借款金额，问至少需要多少现金流才能解决它们之间的债务关系（所有借款都归还）。
例如，下图表示三个朋友P0，P1，P2之间的债务关系，

cashFlow1.png

P0需要归还P1 1000，P0需要归还P2 2000，P1需要归还P2 5000，
如果直接按初始债务关系，需要1000+2000+5000=8000现金。

cashFlow2.png

使用上图中（最佳）还款方案，则只需要3000+4000=7000现金。

---

解决方案

使用贪心方法，每一步都解决一个人的借债关系。如何选择每一步要解决的债务关系人呢？挑选出净借出和净借入最大的两个人，挑他们两个中数值小的那个，如果净借出的值x相对较小，则将净借入最大的人减去x；如果净借入的值x相对较小，则将净借出最大的人减去x。即从最大借入的人转移x到最大借出的人。
算法的具体步骤如下：
设有n个人，P_i，其中i从0到n-1。

1. 计算每个人的净数量。P_i的净数量等于所有借出的和减去所有借入的和。
2. 找到两个人：最大净借出人（正最大）和最大净借出人（负最大），分别为maxCredit和maxDebit。最大净借入人为P_d，最大净借出人为P_c。
3. 设x为maxCredit和maxDebit中的小者，从P_d中消去x，从P_c中消去x。更新P_c和P_d净数量。
4. 若x等于maxCredit，则P_c可以去除（债务已清0)；若x等于maxDebit，则P_d可以去除。
5. 对于剩下的n-1个人，重复上面2-4。
   算法的时间复杂度为O(n^2)。