求思路 - 未名空间MITBBS历史存档

a*a2016-03-15 07:03

1 楼

如果你和另外两个朋友出去玩，每个人付一部分钱，比如你掏了car rent，另一个人
付了hotel等等。最后回家了，你们想AA，最后你们每个人付的钱都一样，写个方法能
返回谁应该给谁多少钱
比如三个人分别掏了5，3，1，那么a[2]应该给a[0] 2 刀
如果现在有n个人的话，应该怎么办
写完了之后，大哥问，最需要多少次transaction，一个人给另一个人钱的话算一次，
我心想的是 O(n – 1) 就是 O(n)，大哥说specific answer, 就是 n – 1次
然后Follow up，如果每次transaction特别麻烦，不管是时间还是空间都特别麻烦。如
果不用考虑everything，不考虑cpu，不考虑硬盘，我们想让这个次数最少，怎么办。

a*e2016-03-15 07:03

2 楼

前部分是个经典题。
后部分不太明白，有例子吗？

办。

【在 a*****a 的大作中提到】

: 如果你和另外两个朋友出去玩，每个人付一部分钱，比如你掏了car rent，另一个人
: 付了hotel等等。最后回家了，你们想AA，最后你们每个人付的钱都一样，写个方法能
: 返回谁应该给谁多少钱
: 比如三个人分别掏了5，3，1，那么a[2]应该给a[0] 2 刀
: 如果现在有n个人的话，应该怎么办
: 写完了之后，大哥问，最需要多少次transaction，一个人给另一个人钱的话算一次，
: 我心想的是 O(n – 1) 就是 O(n)，大哥说specific answer, 就是 n – 1次
: 然后Follow up，如果每次transaction特别麻烦，不管是时间还是空间都特别麻烦。如
: 果不用考虑everything，不考虑cpu，不考虑硬盘，我们想让这个次数最少，怎么办。

T*12016-03-15 07:03

3 楼

最少，最少，是零次。如果每个人刚好花的钱时平均数。

办。

【在 a*****a 的大作中提到】

: 如果你和另外两个朋友出去玩，每个人付一部分钱，比如你掏了car rent，另一个人
: 付了hotel等等。最后回家了，你们想AA，最后你们每个人付的钱都一样，写个方法能
: 返回谁应该给谁多少钱
: 比如三个人分别掏了5，3，1，那么a[2]应该给a[0] 2 刀
: 如果现在有n个人的话，应该怎么办
: 写完了之后，大哥问，最需要多少次transaction，一个人给另一个人钱的话算一次，
: 我心想的是 O(n – 1) 就是 O(n)，大哥说specific answer, 就是 n – 1次
: 然后Follow up，如果每次transaction特别麻烦，不管是时间还是空间都特别麻烦。如
: 果不用考虑everything，不考虑cpu，不考虑硬盘，我们想让这个次数最少，怎么办。

p*22016-03-15 07:03

4 楼

换了我就说，你丫真抠门，我请客！

办。

【在 a*****a 的大作中提到】

: 如果你和另外两个朋友出去玩，每个人付一部分钱，比如你掏了car rent，另一个人
: 付了hotel等等。最后回家了，你们想AA，最后你们每个人付的钱都一样，写个方法能
: 返回谁应该给谁多少钱
: 比如三个人分别掏了5，3，1，那么a[2]应该给a[0] 2 刀
: 如果现在有n个人的话，应该怎么办
: 写完了之后，大哥问，最需要多少次transaction，一个人给另一个人钱的话算一次，
: 我心想的是 O(n – 1) 就是 O(n)，大哥说specific answer, 就是 n – 1次
: 然后Follow up，如果每次transaction特别麻烦，不管是时间还是空间都特别麻烦。如
: 果不用考虑everything，不考虑cpu，不考虑硬盘，我们想让这个次数最少，怎么办。

m*02016-03-15 07:03

5 楼

这个follow up我猜是这个意思：
假设有m个人需要给钱，数目为give[0 ... m-1]，然后有n个人需要收钱，数目为
receive[0 ... n-1]，（sum(give)=sum(receive)）
如果give[i]==receive[j], 那么i给j的钱正好，就是一次交易。如果give[5]=10,
receive[3]=4, receive[8]=6, 那么5要分别给3、8各一次钱，就是2次交易。
现在给定give[]和receive[], 需要求最少交易次数。
想了半天没找到dp的做法，能想到的只有硬搜了，用递归是比较好实现的。有人想到更
好的解法请post。
// 硬搜
int dfs() {
int ans=INT_MAX;
for (int& g : give)
for (int& r : receive)
if (g>0 && r>0) {
int num = min(g,r);
g-=num, r-=num;
ans = min(ans, dfs());
g+=num, r+=num;
}
return ans==INT_MAX ? 0 : ans;
}

办。

【在 a*****a 的大作中提到】

: 如果你和另外两个朋友出去玩，每个人付一部分钱，比如你掏了car rent，另一个人
: 付了hotel等等。最后回家了，你们想AA，最后你们每个人付的钱都一样，写个方法能
: 返回谁应该给谁多少钱
: 比如三个人分别掏了5，3，1，那么a[2]应该给a[0] 2 刀
: 如果现在有n个人的话，应该怎么办
: 写完了之后，大哥问，最需要多少次transaction，一个人给另一个人钱的话算一次，
: 我心想的是 O(n – 1) 就是 O(n)，大哥说specific answer, 就是 n – 1次
: 然后Follow up，如果每次transaction特别麻烦，不管是时间还是空间都特别麻烦。如
: 果不用考虑everything，不考虑cpu，不考虑硬盘，我们想让这个次数最少，怎么办。

a*a2016-03-15 07:03

6 楼

后来我认真想了一下，面试官估计希望用bfs来做，每一步无非就是一个人给了另外一
个人一点钱。然后用这些人付出的钱做状态，然后做遍历就好了，到了大家付出的钱一
样的时候就是最少的步骤。