诗家之绝唱，文青之良药 - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>Joke - 肚皮舞运动

诗家之绝唱，文青之良药

诗家之绝唱，文青之良药# Joke - 肚皮舞运动

b*y2010-08-06 07:08

1 楼

前段时间看到一道Google Intern的题目，没想出来具体怎么做，所以上来请教一下各
位大侠，请不吝赐教。
意思大概是这样的：
一群人要清算相互之间的欠款，要写check给对方。问能不能找出一种还钱的方法，以
至于每个人只要写一张check.
譬如说
A欠B 10刀，
B欠C 10刀，
B欠D 10刀，
D欠C 20刀，
原本B要写两张check的，一张给C,一张给D，
跟好的方法是B只写一张20刀的check给C,而D写一张10刀的check给C
要设计一个算法判断是否存在有这种只写一张check的解。

j*r2010-08-06 07:08

2 楼

会不会吃出问题？

h*k2010-08-06 07:08

3 楼

在我和世界之间加入一个弹簧
收拢，弹开再收拢
直到最后彼此厌倦
把所有走过的路全交给风

h*o2010-08-06 07:08

4 楼

1. Create a matrix like below
A B C D
A 0 10 0 0
B 0 0 10 10
C 0 0 0 0
D 0 0 20 0
2. For each person, caculate the amount as per the matrix
A -10
B -10
C +30
D -10
3. Group negative numbers based on number of positive numbers
For example, there is only one positive, so need only 1 group.
If can't group, return false. (need recursion for grouping)

l*32010-08-06 07:08

5 楼

试试看不就知道了嘛

k*e2010-08-06 07:08

6 楼

不知道是世界弹了你，还是你弹了世界。

【在 h*****k 的大作中提到】

: 在我和世界之间加入一个弹簧
: 收拢，弹开再收拢
: 直到最后彼此厌倦
: 把所有走过的路全交给风

d*i2010-08-06 07:08

7 楼

A B C D
A 0 10 0 0
B 0 0 10 10
C 0 0 0 0
D 0 0 20 0
2. For each person, caculate the amount as per the matrix
A -10
B -10
C +30
D -10

d*32010-08-06 07:08

8 楼

宇宙里有什么中国人不能吃的动物吗？

m*r2010-08-06 07:08

9 楼

其實那都是心中的風，所引發的雞凍。

【在 k****e 的大作中提到】

: 不知道是世界弹了你，还是你弹了世界。

b*y2010-08-06 07:08

10 楼

huduo, 能展开说说怎么group么？
例如：
A B C D E F
A 10 10
B 10 10
C 10 10
D
E 20 10
F
对于每个人
A： -20
B： 0
C： -10
D： 40
E： -20
F： 10
有两个正数，怎么group/group不起来?

R*R2010-08-06 07:08

11 楼

吃完了汇报一下。

h*k2010-08-06 07:08

12 楼

带一根弹簧到作者面前，为我们守护整个世界。

【在 k****e 的大作中提到】

: 不知道是世界弹了你，还是你弹了世界。

h*o2010-08-06 07:08

13 楼

Create an array, and pass each item
For example,
int amount[4];
for(int i=0;i<4;i++)
amount[i]=0;
A欠B 10刀，amount[0]-=10;amount[1]+=10;
B欠C 10刀，amount[1]-=10;amount[2]+=10;
B欠D 10刀，amount[1]-=10;amount[3]+=10;
D欠C 20刀，amount[3]-=20;amount[2]+=20;
amount[0]=-10;
amount[1]=-10;
amount[2]=30;
amount[4]=-10;

【在 d*********i 的大作中提到】

: A B C D
: A 0 10 0 0
: B 0 0 10 10
: C 0 0 0 0
: D 0 0 20 0
: 2. For each person, caculate the amount as per the matrix
: A -10
: B -10
: C +30
: D -10

S*p2010-08-06 07:08

14 楼

最好别吃。以我的经验，野兔吃草，美国这里的草都是洒了杀虫剂了的，野兔体内肯定
积累了很多这样的杀虫剂。
杀虫剂可能毒不死人，但是可能会使人变得胆小从而做出意想不到的事情来。
详情请参见X-File Season 2, Episode 3 "Blood", Kill 'EM All!

m*d2010-08-06 07:08

15 楼

人和世界之间
无论是一个避孕套
还是一根橡皮筋
直到有一天
没有了弹性

【在 h*****k 的大作中提到】

: 在我和世界之间加入一个弹簧
: 收拢，弹开再收拢
: 直到最后彼此厌倦
: 把所有走过的路全交给风

h*o2010-08-06 07:08

16 楼

按正负数，先分成两组
group1: 20,10,20
group2: 40,10
问题就变成了，有一个arrary，几个sum，怎么把array里的整数分组，使得每一组的
sum等于
each sum？
if sizeof(group1)return false;
Sort group1 and group2, so
group1: 10,20,20 (size:n)
group2: 10,40 (size:m)
if(group1[0]>group2[0] || group1[n]>group[m])
return false;
foreach(i in group1)
{
if(i in group2)
remove i from group1 and group2;
}
so,
group1: 20, 20 (size:n)
group2: 40 (size:m)
for(int i=1;i{
sum group1[0]+group1[1]...
if(the sume == group2[0])
remove each items in the sum from group1
remove group2[0]
recursion/loop
}

【在 b******y 的大作中提到】

: huduo, 能展开说说怎么group么？
: 例如：
: A B C D E F
: A 10 10
: B 10 10
: C 10 10
: D
: E 20 10
: F
: 对于每个人

c*o2010-08-06 07:08

17 楼

吃完了还活着的话来update一下口感

h*k2010-08-06 07:08

18 楼

带着避孕套
上路吧
为你祝福
勇士

【在 m*****d 的大作中提到】

: 人和世界之间
: 无论是一个避孕套
: 还是一根橡皮筋
: 直到有一天
: 没有了弹性

h*62010-08-06 07:08

19 楼

使用链式传递付帐法，先在欠款人之间传递，每人加上自己的应付款交给下一个人。然
后在收款人之间传递，每人减去自己的应收款交给下一个人。

R*R2010-08-06 07:08

20 楼

看不到update就有可能....

【在 c****o 的大作中提到】

: 吃完了还活着的话来update一下口感

k*e2010-08-06 07:08

21 楼

给我一根弹簧，将我弹去月亮，本有嫦娥吴刚，加我一个不黄。

【在 h*****k 的大作中提到】

:
: 带着避孕套
: 上路吧
: 为你祝福
: 勇士

f*g2010-08-06 07:08

22 楼

1) Model the question as a Directed Graph: A node represents a person; A
directed edge from node A to node B represents person A owns the money to
person B; the weight for each directed edge represents how much money it
owns.
2) Set the rules to combine/remove the the directed edges:
2.1) if the graph contains circles, then remove the edge with minimum
weight, and minus the minimum weight to other edges on the circle.
2.2) If node A has multiples paths to reach node B, always choose the
longest path. Then we could pass the weight to the next node on the path.

d*92010-08-06 07:08

23 楼

想吃，抓不住，用枪射，不忍心。

【在 j***r 的大作中提到】

: 会不会吃出问题？

h*k2010-08-06 07:08

24 楼

还有玉兔捣药，常常八戒串门，若是玉帝亲临，不如归来随风。

【在 k****e 的大作中提到】

: 给我一根弹簧，将我弹去月亮，本有嫦娥吴刚，加我一个不黄。

d*i2010-08-06 07:08

25 楼

学习了！

Z*e2010-08-06 07:08

26 楼

呵呵，给你讲个故事。
话说有一对中国 Couple 带着一孩子来到美国，发现美国没有计划生育，就想再要孩子
。努力造人很久都没成功，就去看医生，结果医生发现在他们体内，有给鸽子吃的避孕
药（美国为了控制鸽子数量，鸽子食物里掺有避孕药）。
还需要再多说吗？呵呵。

【在 j***r 的大作中提到】

: 会不会吃出问题？

v32010-08-06 07:08

27 楼

不黄是啥？尿不黄？

【在 k****e 的大作中提到】

: 给我一根弹簧，将我弹去月亮，本有嫦娥吴刚，加我一个不黄。

z*n2010-08-06 07:08

28 楼

靠，我自己写过一个出去玩以后回来分账还钱的程序，核心问题就是这个，老美不都是
当场aa吗，居然google能问到这个。。。
就是算一下每个人总共欠别人多少刀就行（欠款为负就表示别人欠他），跟楼下给的算
法思路差不多

【在 b******y 的大作中提到】

: 前段时间看到一道Google Intern的题目，没想出来具体怎么做，所以上来请教一下各
: 位大侠，请不吝赐教。
: 意思大概是这样的：
: 一群人要清算相互之间的欠款，要写check给对方。问能不能找出一种还钱的方法，以
: 至于每个人只要写一张check.
: 譬如说
: A欠B 10刀，
: B欠C 10刀，
: B欠D 10刀，
: D欠C 20刀，

c*o2010-08-06 07:08

29 楼

你是说米国的兔子是吃避孕药长大的？

【在 Z***e 的大作中提到】

: 呵呵，给你讲个故事。
: 话说有一对中国 Couple 带着一孩子来到美国，发现美国没有计划生育，就想再要孩子
: 。努力造人很久都没成功，就去看医生，结果医生发现在他们体内，有给鸽子吃的避孕
: 药（美国为了控制鸽子数量，鸽子食物里掺有避孕药）。
: 还需要再多说吗？呵呵。

k*e2010-08-06 07:08

30 楼

更有月桂一支，风来为我舞诗，风去尤自回头，风灭沉静如痴。

【在 h*****k 的大作中提到】

:
: 还有玉兔捣药，常常八戒串门，若是玉帝亲临，不如归来随风。

K*g2010-08-06 07:08

31 楼

你这个要先排一下序吧？

【在 h**6 的大作中提到】

: 使用链式传递付帐法，先在欠款人之间传递，每人加上自己的应付款交给下一个人。然
: 后在收款人之间传递，每人减去自己的应收款交给下一个人。

q*n2010-08-06 07:08

32 楼

活该呀。

【在 Z***e 的大作中提到】

k*e2010-08-06 07:08

33 楼

他俩黄与不黄，并不因我更张。我有耳塞十付，再黄也入梦乡。

【在 v3 的大作中提到】

: 不黄是啥？尿不黄？

h*62010-08-06 07:08

34 楼

不需要排序，遍历两次数组即可。第一次把沿负的传递一遍，第二次沿正的传递一遍。

p*l2010-08-06 07:08

35 楼

最好别吃，万一携带什么病毒就不好了

h*k2010-08-06 07:08

36 楼

八戒自惭形秽，吴刚心如死灰，风去遍地凌乱，不复嫦娥春闺。

【在 k****e 的大作中提到】

: 更有月桂一支，风来为我舞诗，风去尤自回头，风灭沉静如痴。

h*t2010-08-06 07:08

37 楼

这个算法是错的。
比如a须付20，bc各收10
安装这个算法是无解的，但是正确解法是a写20给b，b写10给c
另一个人说的链式算法是对的。

【在 h***o 的大作中提到】

:
: 按正负数，先分成两组
: group1: 20,10,20
: group2: 40,10
: 问题就变成了，有一个arrary，几个sum，怎么把array里的整数分组，使得每一组的
: sum等于
: each sum？
: if sizeof(group1): return false;
: Sort group1 and group2, so

j*b2010-08-06 07:08

38 楼

这个故事我觉得有点假。如果真的给鸽子用这样的有residual的避孕药，那不是给吃鸽
子的鹰也避孕了么？

【在 Z***e 的大作中提到】

m*d2010-08-06 07:08

39 楼

打油诗为什么容易传染，这是个学术问题

【在 h*****k 的大作中提到】

:
: 八戒自惭形秽，吴刚心如死灰，风去遍地凌乱，不复嫦娥春闺。

g*s2010-08-06 07:08

40 楼

这个算法如果是大家都用cash分可以。
但按题目说的是要用check怎么办呢，check无法传递，也就是说每人必须事先知到
check开给谁和开多少钱，而且只能一张check。

【在 h**6 的大作中提到】

: 不需要排序，遍历两次数组即可。第一次把沿负的传递一遍，第二次沿正的传递一遍。

p*r2010-08-06 07:08

41 楼

中国学生吃什么动物被抓被遣送都快成urban legend了

【在 j***b 的大作中提到】

: 这个故事我觉得有点假。如果真的给鸽子用这样的有residual的避孕药，那不是给吃鸽
: 子的鹰也避孕了么？

k*72010-08-06 07:08

42 楼

链式算法可以找出这样的一个解。
但是问题是，题目是要求判断有没有这样一个解，而不是解是什么，所以应该有更快速
的算法回答。或
者说，在什么样的情况下不存在这样一个解？

【在 b******y 的大作中提到】

z*o2010-08-06 07:08

43 楼

感觉可信度不大高
这家人天天拿鸽子当鸡肉吃？鸽子好像不便宜吧。
如果一周一只，体重约在一lb左右的鸽子体内残存的那点药有这么强劲？

【在 Z***e 的大作中提到】

k*72010-08-06 07:08

44 楼

这样看来，任何情况下都能够找到这样一个每人只写一张check的解了？那题目要判断
有没有这样一个
解是什么意义？

【在 h**6 的大作中提到】

: 使用链式传递付帐法，先在欠款人之间传递，每人加上自己的应付款交给下一个人。然
: 后在收款人之间传递，每人减去自己的应收款交给下一个人。

h*72010-08-06 07:08

45 楼

这故事是 imply 他们射杀鸽子吃吧

【在 z****o 的大作中提到】

: 感觉可信度不大高
: 这家人天天拿鸽子当鸡肉吃？鸽子好像不便宜吧。
: 如果一周一只，体重约在一lb左右的鸽子体内残存的那点药有这么强劲？

y*52010-08-06 07:08

46 楼

假如B再欠E钱，而其他人都和E没关系，那么就无解。
我觉得这个可能得对每个人判断能否找到一个有向路径覆盖他的所有债主。对于一个返
回True/False
的函数来说总感觉时间复杂度比较高。

【在 k*****7 的大作中提到】

: 这样看来，任何情况下都能够找到这样一个每人只写一张check的解了？那题目要判断
: 有没有这样一个
: 解是什么意义？

z*o2010-08-06 07:08

47 楼

我以为是imply他们偷鸽子食吃呢

【在 h*****7 的大作中提到】

: 这故事是 imply 他们射杀鸽子吃吧

k*72010-08-06 07:08

48 楼

这种情况也是可以的吧，按链式算，每个人算欠别人多少，别人欠自己多少，确定要支
出或收益的净
值。然后支出人把钱逐一链式传递到一个支出人那里，然后那个人把总数（加上自己的
）付给一个收益
人，然后这个收益人留下自己的部分，再把剩下的钱在收益人组传递下去。
比如 A欠B20，B欠C20， B欠D10，这样A净值-20，B净值-10，C净值20，D净值10，于是
A -> B 20
B -> C 30
C -> D 10
我于是死活也想不出来什么情况下无解。。。

【在 y******5 的大作中提到】

: 假如B再欠E钱，而其他人都和E没关系，那么就无解。
: 我觉得这个可能得对每个人判断能否找到一个有向路径覆盖他的所有债主。对于一个返
: 回True/False
: 的函数来说总感觉时间复杂度比较高。

s*y2010-08-06 07:08

49 楼

lmao

【在 z****o 的大作中提到】

: 我以为是imply他们偷鸽子食吃呢

f*i2010-08-06 07:08

50 楼

我觉得其实有一种最简单的O(n)算法。
按照上面的方法，算出每个人究竟是付钱多还是收钱多，
假设人员a,b,c,d都是付的钱比收的钱多，无论要多付多少
人员e,f,g,h都是收的钱比付的多
解法如下：
a，b,c,d把钱全部给e
e把收到的钱减去应得的钱，然后pass给f
f把收到的钱减去应得的钱，然后pass给g
g把收到的钱减去应得的钱，然后pass给h
完毕
guaranteed everyone signs only one check

a*o2010-08-06 07:08

51 楼

俺家前后院经常有野鹿光顾。把俺的花园当FREE SALAD BAR。你快带上枪来打吧。

h*t2010-08-06 07:08

52 楼

有解的，b写多余他欠e的钱给e,e写多出的钱给另一个人

【在 y******5 的大作中提到】

c*p2010-08-06 07:08

53 楼

每次看到这种帖子都很无语。饿死鬼投胎吗？只要能不要钱的，都想往嘴里塞。难怪国
内生态这么差。店里那么多吃的，不会去买吗？没钱说一声，大家帮点没事。成天惦记
打点兔子，弄点松鼠，丢人丢到家了真是！！！

y*52010-08-06 07:08

54 楼

看来我对题意理解有误。我以为一个人只能给他的债主写check，也就是说，在有向图
中我们只能减少
某个点的已有出度边。
如果e可以代替b向"b的而非e的"的债主还钱，感觉总是有解啊，这题目还要我们判断什
么？能说说你的
理解么？

【在 h*t 的大作中提到】

: 有解的，b写多余他欠e的钱给e,e写多出的钱给另一个人

c*p2010-08-06 07:08

55 楼

吃死了才好呢！！！

t*M2010-08-06 07:08

56 楼

小兔子多可爱，你忍心吗？？