感谢分享 已收藏

不一定把，如果是奇数个数的数组呢，而且首尾相加的和有可能是最小，中间两个相加和是最大的情况

6666666666666666

确实能提高呀~

ping3014 发表于 2016-3-29 23:36
举个例子验证一下：也是12个数，如下：
1,2,3,10,20,30,40,50,60,100,200,300
不一定能实现吧？ ...

可以实现的 首先a,b数组都是n,然后c数组元素就是2n,保证了元素个数是偶数.我这个思路来源于高斯的1-100的求和思想, 1+100 = 2+ 99=101,所以这样得到的差才会最小

ipursue 发表于 2016-3-30 10:05
好题，很考验思维逻辑，数学思想不好的很难想到

就是想到了高斯的求和原理,才这样做的

onceIme 发表于 2016-3-30 14:58
不一定把，如果是奇数个数的数组呢，而且首尾相加的和有可能是最小，中间两个相加和是最大的情况 ...

可以实现的 首先a,b数组都是n,然后c数组元素就是2n,保证了c的元素个数是偶数.

我觉得隔着一个取比较好,arr数组取crr数组偶数索引的元素,brr数组取crr数组奇数索引的元素,不然当crr数组不是等差数列,并且差异较大时,可能楼主的方法不是最满足题意的:
                for (int i = 0;i < crr.length;i++ ) {                        
                        if (i % 2 == 0) {                              //arr数组取crr数组偶数索引的元素
                                 arr[i / 2] = crr[i ];
                         }else {                                           //brr数组取crr数组奇数索引的元素
                                 brr[(i - 1) / 2]= crr[i ];
                         }
                 }
当然,就算这样也有可能不能保证差异最小,最保险的方法是在限制条件的情况下遍历所有可能,找出最小差异的两组数组.
如有不对,还请指正.

xiaofushen 发表于 2016-3-30 22:09
我觉得隔着一个取比较好,arr数组取crr数组偶数索引的元素,brr数组取crr数组奇数索引的元素,不然当crr数组不 ...

嗯嗯,这个思想也是正确的,不过最优方案,我也不能确定.我也是看到了这个题,自己做了一下,和大家分享一下.

灵魂灬丿丶轩 发表于 2016-3-30 22:34
嗯嗯,这个思想也是正确的,不过最优方案,我也不能确定.我也是看到了这个题,自己做了一下,和大家分享一下. ...

关于最优方案,我再想想,顺便问一下楼主是0310的吗?我也是啊.

灵魂灬丿丶轩 发表于 2016-3-30 21:08
可以实现的 首先a,b数组都是n,然后c数组元素就是2n,保证了元素个数是偶数.我这个思路来源于高斯的1-100的 ...

c = ｛1，2，3，10，20，30，40，50，60，100，200，300｝这个数组按照你的算法分成
a = ｛1，2，3，100，200，300｝和是606，b = ｛10，20，30，40，50，60｝和是210，两个数组
差是396
看题目没要求分成两个长度一样的数组，那么差最小的应该是
c = ｛1，2，3，40，60，100，200｝和是406，d = ｛10，20，30，50，300｝ 和是410，两个数组
差是4
高斯求1-100和是因为1-100是等差数列，而 c 的元素不是一个等差数列
我的思路是求 c 的和，然后除以2得到一个数x，让 a 数组的和尽可能接近x。
初步设想伪代码如下：int index = c.length-1;
max = c[index];        如果 max > x 就让 a = ｛max｝，其余元素组成 b，否则执行下面循环
for(i = index, i >= 0, i--) {            反向遍历数组 c
     if(c[index] < x ) {
         将 c[index] 加入 a 数组
         index-- ；
         x -= c[index]
     }
}
结果就取出了300，100，3，2，1
和是406
其余的数是200，60，50，40，30，20，10
和是410

好题，学习了