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

醉卧水云间

原帖由 anthony1983 于 2008-3-2 20:40 发表
就是一个枚举题~~~反复交换，直到两个数组和差值最小。
枚举过程可优化~

一个天平没有刻度, 你还能优化? 服了.

cugb_cat

貌似是一个0－1背包问题。

kuhuo4321

确实有点棘手

[ 本帖最后由 kuhuo4321 于 2008-3-3 17:12 编辑 ]

kuhuo4321

首先要明白一点，问题的关键是要分出10个球中最重的5个球，这样重量差才会达到最大：
10个球的问题可以简化成4个球来看
第一步： 4个球编号1，2，3，4；
第二步： 从1开始分别和其他比较，对每个编号都使用一个量标记V1~V4，每次比较重量大的就对这个变量+1，小的-1
第三步： 1号球分别和2，3，4比较(假如1号球最大，那么变量分别为V1++,V2--,V1++,V3--,V1++,V4--)；2号球分别和3，4比较；3好球和4比较；结束。可以看到比较次数是一个C(4,2)=6 次，10个球就是C(10,2)=45次（-。-确实够暴力的），可能不是最好的办法，但是确实可以解决问题。
第四步：所有的比较完成后，对每个球的标记变量Vn，取2个最大的值就是最大的了。

以上是4个球的解决方法，有点像穷举，我目前还找不到更简单的方法。
10个球以此类推，只不过要比较45次，的确有点暴力，如果有更好的方法请指教。

[ 本帖最后由 kuhuo4321 于 2008-3-3 17:37 编辑 ]

dakacha

很早的微软试题，国内鲜有公司出高水平的考试题，凡有类似考题，大都是偷来的，给公司装门面哪，不知道考官自己能否迅速作答。

benjiam

应该是1：1 比较 分成 轻重2堆。
然后2堆分别排序， 然后合成一个列。
合成不是简单的加在一起， 不断拿最那堆和 重堆里面最轻的比较，类似冒泡的算法

在一个队列以后
那就是
先左10  右边9
不断向轻那边的加石头 8,7 ,6 这样的顺序。
.如果轻的变成重的了就反过去加另外一边。一直延续下去。在此同时如果有一边已经变有5个了 就把剩下的加到另外一边

10  是  最重的那个
1   是最亲那个


我的答案一定是对的！！！！！！！！确信。  大概用了2-3分钟。

[ 本帖最后由 benjiam 于 2008-3-3 22:19 编辑 ]

大漠guyan

确实有点棘手

HJLin

10个选5个，共n中方案
排序，最中间两项是最佳答案
当然比较耗时间了

epegasus

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

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

有可能是对的，但缺乏证明。