今天面试栽在这个小题上了

cugb_cat

原帖由 ssffzz1 于 2008-3-5 12:07 发表
题目要求是要求重量差最小。

既然顺序都出来了。那么把1 10 3 8  5放到一边，2 9 4 7 6的放到另一边。自然是重量差最小。

这样明显是错的，看下面这个例子：
假设已排好序的10个球的重量分别是：
1,3,4,6,7,10,20,25,30,100
如果按照你的方法，那么得到的结果是1,100,4,25,7在一边，3,30,6,20,10在另一边，两边的差是137-69=68.

而1,3,4,6,100在一边，7,10,20,25,30在另一边的这种分法的差值是114-92=22,明显比你的方法小。

cugb_cat

原帖由 ssffzz1 于 2008-3-5 12:07 发表
题目要求是要求重量差最小。

既然顺序都出来了。那么把1 10 3 8  5放到一边，2 9 4 7 6的放到另一边。自然是重量差最小。

这种方法在各球重量之差差不多时才较为管用，而且也不保准，所以要搜索全部可能的情况，搜索过程中进行优化。

ssffzz1

哦，谢谢。
也对啊。这样的话这个题似乎就是无解了。因为不知道各个小球间的差异大小。

bysfc

这样的公司不去也罢

cugb_cat

原帖由 ssffzz1 于 2008-3-5 13:32 发表
哦，谢谢。
也对啊。这样的话这个题似乎就是无解了。因为不知道各个小球间的差异大小。

我也这么觉得，因为不知道10个球具体重量是多少，如果10个球的重量能够做为参数输入，那么这个题还是有解的。

chuny

我觉得是这样,把10个球分成两组,编上号码后放在天平两边,然后通过多次的交换,使天平趋于于平衡.如果穷尽了各种组合 自然能找到唯一答案.

yangtou

前面有个人已经说出解法了，两组中重的那一组最轻的分法就是答案，直接一个一个比较就可以了

NalaGinrut

原帖由 benjiam 于 2008-3-4 22:41 发表



在这种情况下，下一个最轻的只能是5了，  这个是错误的。  

我首先排过一次序的， 所以会是10 5 4 3 2 1 这样的顺序。不会出现10 4 3 2 1 5 这样的顺序。


比1小？  你目前最轻的球 是1 个单位了  ...

0.9,0.8是什么？你定的权重？
那么无论你如何定权重，编号是不会变的，我是问你编号为5的球去哪里
下一个最轻的不是编号为5的球，莫非是>5的？
注意我问的是编号

NalaGinrut

原帖由 benjiam 于 2008-3-3 17:56 发表
应该是1：1 比较 分成 轻重2堆。
然后2堆分别排序， 然后合成一个列。
合成不是简单的加在一起， 不断拿最那堆和 重堆里面最轻的比较，类似冒泡的算法

在一个队列以后
那就是
先左10  右边9
不断向轻那 ...

你的方法说白了就是两个阶段：
1、merge排序
2、补差法
merge没问题，但是补差的时候如果你放到称上的球不能拿下来，那一定可能出现我说的那种情况
如果可拿下来重新做比较，那是可以确保没问题，只是效率低些

qiyongquan

去华为经常被问道排序题