先各自排序,再交叉存放较大无素
这个基本可行，但不是交叉存放较大元素，而是哪边的和小就一直放大元素，直到n，然后把剩下的扔到另一组中就ok了。 for (i=0; i<N; i++)
{
for (j=0; j<N; j++)
{
change(a+i, b+j);
if (abs(sum(a)-sum(b)) > ab_diff)
{
change(b+j, a+i);//如果不能使差值变小，则交换回去，也就是说不交换
}
else
{
ab_diff = abs(sum(a)-sum(b));//更新差值
}
}
}
TC2测试
原帖由 namtso 于 2006-11-13 17:16 发表
我相信，这个题在8分钟内能写出代码来的人，绝对是大大的牛人。
我觉得应该这样：
a和b 分别求出累加和，得出累加和的差c1，然后循环查找找a中的某个元素a，使得a与b中的某个元素b交换之后，得出一个 ...
[ 本帖最后由 greensky_34 于 2006-11-13 20:29 编辑 ] 我有个想法，利用天平的原理：
１．两端各有n个元素．其总重分别为：W1, W2,差为diff_w(W1,W2)
２．结束条件是，diff_w(W1,W2)小于等于左右两边中任意元素之差的最小值．
３．如果不满足上述条件则进行置换，置换的规则是，将上述两边任意二元素之差最接近diff(w1,w2)得元素进行置换．.再重复上述步骤． 原帖由 hithotwinds 于 2006-11-13 10:16 发表
刚学编程两个月，不知道思路是否正确，错就一定有的。
#include"stdio.h"
com(int a,int n)
{int i,j,p,q,s;
for(i=0;i<2*n-1;i++)
{
a=q,p=i;
for(j=i+1;j<2*n;j++)
...
才两个月能写出这么长的程序还是不错滴。。。
加油！！ 原帖由 ccjjhua 于 2006-11-13 11:42 发表
把a,b 2数组的元素放到数组3（2n大小） 中进行排序，
a 先取最小的，b先取次小的，
然后根据a,b已取元素和的大小来决定谁来取剩下元素中最小的。策略是，已取得的所有元素之和大的来取C中剩下元素中的最小者。如 ...
这种方法似乎很可行:D 我写了80分钟，未果
当时心想，TMD，难道这是google面试题吗 小弟觉得这个题目应用动态规化来解：
原问题与下问题应该属同类。
有一组数a1,a2,a3,...,an. 求出一个子串，其各元素的和总元素和的一半差值最小！设总元素和为sum，
子串和为s_sub.差值为dis,表示第 i个元素到j 个元素之间的子串和。每个元素有两种状态，1为选，0为不选。
当 i==j 时 dis = a = a
当 i<j时 dis = min{sum-s_sub-a, sum-s_sub}
这是大概思想，如有错误望请正！ 原帖由 greensky_34 于 2006-11-13 20:25 发表
for (i=0; i<N; i++)
{
for (j=0; j<N; j++)
{
change(a+i, b+j);
if (abs(sum(a)-sum(b)) > ab_diff)
{
change(b+j, ...
不行阿，我理解后用c实现，结果不正确，可能是我理解有问题？
#include <iostream>
using namespace std;
void change(int* a, int* b) {
int t = *b;
*a = t;
*b = *a;
}
int diff(int a, int b) {
return abs(a - b);
}
int main() {
const int N = 3;
int a[] = {1, 2, 3};
int b[] = {0, 0, 99};
const int sum_a = 6;
const int sum_b = 99;
int ab_diff = abs(sum_a - sum_b);
for (int i=0; i<N; i++) {
for (int j=0; j<N; j++) {
change(a+i, b+j);
if (abs(sum_a - sum_b) > ab_diff)
{
change(b+j, a+i);//如果不能使差值变小，则交换回去，也就是说不交换
}
else
{
ab_diff = abs(sum_a - sum_b);//更新差值
}
}
}
for (int i = 0; i < N; ++i) {
cout << a << " ";
}
cout << endl;
for (int i = 0; i < N; ++i) {
cout << b << " ";
}
cout << endl;
}
回复 1楼 forrestgang 的帖子
>>有两个数组a,b，大小都为n,数组元素的值任意，无序；>>要求：通过交换a,b中的元素，使数组a元素的和与数组b元素的和之间的差最小
这个与下面的等效。
数组 a:a1,a2, a3, ... an;
b:b1, b2, b3, ...bn;
先从 a 中取 x 个元素， 再和 b 中的 n-x 个元素，把他们的值相加， 得 sumi;
再从 a 中取剩下的 n-x 个元素， 和 b 中的 x 个元素，把他们的值相加， 得 sumj;
取 |sumi - sumj| 的绝对值为 subsum;
x 从 0 开始取到 n, 每次得到一个 subsum, 最小的那个 subsum 即所求的情况。
：）。
大概就是这样的，用循环，呵呵。 1.求和并除二, 记为 AVG
2.用短的数组长度个的数字排列组合, 找最接近 AVG 的.
3.把这几个数填入短数组, 其余填入长数组.
不知道这道题中是否要求输出换的步骤, 如果需要, 小 CASE. 不说了.