互相欠账其实可以看成是一个整体,只要保证在事实上收到了借出去的钱(不管是谁还的) 和 还了借来的钱(不管还给谁) 就可以平账。 例如: 1欠2: 5, 3欠4: 5, 实际上1还给4,5块钱 然后3还给2,5块钱也是可以的
或者可以看成有个中央银行,欠钱的人只需要还给银行,而要钱的人只需要问银行要。我们要做的就是调度银行,怎么样能最少的还钱。
在此基础上,我们遍历每一个人,如果这个人账单空的,那么下一个人,如果不空
- 欠钱: 那么随便找个 被欠的人还钱
- 要钱: 那么随便找个 欠钱的人要钱 因为账单已经全部上交给银行了,所以这个人不管是还钱还是要钱都已经完成了一次transaction. 最理想的情况是还给了刚好欠一样金额的人,这样可以少一次transaction