狗狗惨烈电面

This problem can be done by general way:
go through the array starting at index 1, for each element larger than the average, give the superfluous money to the first guy
go through the array starting at index 1, for each element smaller than the average, the first guy give its money to make him to average.

zyoppy008 发表于 2016-9-8 06:41
你这种不行吧。
你看比如 1 3 5 7 9 11 13
3 缺少4个 对吧， 1总共最开始总共只有1个，所以给不了

请仔细审题。。。

ivanml 发表于 2016-9-8 03:31
这题是个数学问题，最后你发现是一个公式，假设ABCDE 5个人，分别花了nums = {1, 2, 3, 4, 5}，假设从A的角 ...

按照楼主的意思，那1给0号$1，那array等于变成了2，1，3，4，5，之后0号给2号0，0号给3号$1，就变成了1，1，3，5，5，然后0号给4号 $2，那不就给不了了么？不是很明白，麻烦楼主解释一下

补充内容 (2016-9-8 08:40):
是我想错了。。。。已经明白了

Crystal_yy 发表于 2016-9-8 08:31
按照楼主的意思，那1给0号$1，那array等于变成了2，1，3，4，5，之后0号给2号0，0号给3号$1，就变成了1， ...

我发现很多人题意没理解清楚。。题目的input array是指每个人“花出”了多少钱，所以nums[0] = 1表示0号花了1刀，然而平均是每人应该花3刀，所以0号少花了，所以才要0号给其他人钱。
1号给0号1刀之后，nums[0]变成0而不是1，因为0号收到了1号的钱，他“花”的更少了，但是接下来：
0 gives 2 $0
0 gives 3 $1
0 gives 4 $2
最后nums[0] = 3也就是变成了平均的钱，你可以遍历这个输出会看到最后每个index都会变成3.

ivanml 发表于 2016-9-8 08:41
我发现很多人题意没理解清楚。。题目的input array是指每个人“花出”了多少钱，所以nums[0] = 1表示0号 ...

是的，谢谢解释，看到脑子乱了，想反了，之后才反应过来犯了弱智错误

ivanml 发表于 2016-9-8 07:17
请仔细审题。。。

那就一遍循环就可以

ivanml 发表于 2016-9-8 04:36
这个输出的时候遇到负数改一改format不就好了么。。我觉得解答肯定不是唯一的，除非面试官要求least tran ...

least transaction是NP Complete...

hxtang 发表于 2016-9-8 11:10
least transaction是NP Complete...

是的 ksum k从小到大做

其实感觉思路就是大家少给的都把钱给一个人，这里是0号，然后0号再把钱发给多给钱的。。。。。想法挺好的。

我去  这是我onsite的题。。。