Google面经——一道可能被大家低估的题

是N角债问题吗？N个人有欠钱的，有借钱的，但是总体balance是0。问最少多少次交易可以让所有人不欠钱也不被欠？
如果是这个问题的话，最多N-1次交易（每次交易至少有一个人的balance变成0），最少的交易次数可以用BFS搜一下。

mark,只会写naive的，坐等大牛代码

lzb700m 发表于 2016-9-16 21:30
是N角债问题吗？N个人有欠钱的，有借钱的，但是总体balance是0。问最少多少次交易可以让所有人不欠钱也不被 ...

我不知道你怎么搜……

zsj2725 发表于 2016-9-16 20:23
应该是指能够结清吧
类似（a,b,1) + (b,a,1)
或者 (a,b,2)+(b,c,2)+(c,a,2)

没错 是指能结清

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

这题的做法就是，算清各自应得/应付账款之后，分为正数负数两个集合，0扔掉，然后在正数里面找最小的子集，负数里面找另一个子集，使得存在两个不等于全集的子集，他们的和是相反数，然后合并这两个集合，这样一定是最优的。而找子集的过程就是subset sum，目前看只能穷举，要是你多项式时间做出来，那就图灵奖了。

是面试的时候被指出这其实是NPC问题，还是之后lz想到的？

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies