有两个数组a,b，大小都为n,数组元素的值任意，无序；
要求：通过交换a,b中的元素，使数组a元素的和与数组b元素的和之间的差最小
zhhui2000 回复于：2006-11-13 07:54:20
先各自排序,再交叉存放较大无素
namtso 回复于：2006-11-13 08:33:11
难度太大。
RedPhoenix 回复于：2006-11-13 09:10:21
负数差是不是不考虑？
RedPhoenix 回复于：2006-11-13 09:14:10
2楼的算法应该是得不出最小差的
sithui 回复于：2006-11-13 09:33:38
先整体排序，再交叉取数
mike_chen 回复于：2006-11-13 09:34:14
放到一个临时数组里排序后，两头取，分别存在a,b里
hithotwinds 回复于：2006-11-13 10:16:50
刚学编程两个月，不知道思路是否正确，错就一定有的。
#include"stdio.h"
com(int a[2000],int n)
{int i,j,p,q,s;
for(i=0;i<2*n-1;i++)
{
a[0]=q,p=i;
for(j=i+1;j<2*n;j++)
if(a[j]>q)
{q=a[j];p=j;}
if(i!=p)
{a=s;
s=a[p];
a[p]=a;
}
return(a[2*n-1);
}
for(i
main()
int a[1000],b[1000],c[2000],n,j,k,p,q;
printf("input two same struct array and same long\n");
scanf("%d",&n);
printf("input first struct array");
for(i=0;i<n;i++)
scanf(%d",a);
printf("input secend struct array");
for(i=0;i<n;i++)
scanf(%d",b);
for(i=0;i<n;i++)
c=a;
for(i=0;i<n;i++)
c[n+i+1]=b;/*结合两组数据*/
c[n+i+1]=[com(c[n+i+1],n);/*并排列大小*/
for(i=0;i<n;i++)
{a=0;
b=0;}/*清0*/
a[0]=c[0];
b[0]=c[1];
s=1;
t=1;
p=0;
q=0;
for(i=2;i<2*n-1;i++)
{
if(s==n-1)\*判断是否已经分好了一个数组*\
{for(i=n+t-1;i<2*n-1;i++,t++)
b[t]=c[n+t-1];
break;}
if(t==n-1)\*判断是否已经分好了另一个数组*\
{for(i=n+s-1;i<2*n-1;i++,s++)
b[s]=c[n+s-1];
break;}
for(j=0;j<s;j++)
p+=a[j];\*求数组a[j]的值*\
for(j=0;j<t;j++)\*求数组a[j]的值*\
q+=b[j];
if(p>q)\*判断已经分好的数组大小，并分配下一数值到较少的数组*\
{c=b[t];
t++;}
else{c=a[s]
s++;}
}
for(i=0;i<n;i++)
printf("a=%d ",a);
printf("\n");
for(i=0;i<n;i++)
printf("b=%d ",b);
getch();
}
[ 本帖最后由 hithotwinds 于 2006-11-13 10:25 编辑 ]
yg 回复于：2006-11-13 10:17:22
全部加起来除2，然后试算
12013396 回复于：2006-11-13 10:47:02
设一个变量，类似于天平的指针,就像用天平称东西一样，只不过用变量来记录他们之间的差。然后，根据这个差对下次比较的双方进行调整,再对这个差进行调整，如此反复。不知可否??
[ 本帖最后由 12013396 于 2006-11-13 10:59 编辑 ]
la.lune 回复于：2006-11-13 10:55:13
放到一个临时数组里排序后，两头取，分别存在a,b里
同意~
[ 本帖最后由 la.lune 于 2006-11-13 10:56 编辑 ]
cugb_cat 回复于：2006-11-13 11:06:56
将两个数组都放到一个数组里,然后对这个数组从大到小进行排序,然后将排好序的数组的第一个元素减第二个元素,第三个元素减第四个元素.....一直到第2n-1减第2n个元素,然后求和就得到最小的差值了.排序可以用stdlib.h中的qsort函数,该函数提供的是快速排序算法.
ccjjhua 回复于：2006-11-13 11:42:08
把a,b 2数组的元素放到数组3（2n大小） 中进行排序，
a 先取最小的，b先取次小的，
然后根据a,b已取元素和的大小来决定谁来取剩下元素中最小的。策略是，已取得的所有元素之和大的来取C中剩下元素中的最小者。如此反复，直到取完。每次都是a,b各取一个。
forrestgang 回复于：2006-11-13 13:58:16
引用：原帖由 zhhui2000 于 2006-11-13 07:54 发表
先各自排序,再交叉存放较大无素
这样应该不行:shock:
forrestgang 回复于：2006-11-13 13:59:39
引用：原帖由 yg 于 2006-11-13 10:17 发表
全部加起来除2，然后试算
面试官说了不能用枚举
hydonlee 回复于：2006-11-13 14:14:50
同意楼上.
先对两个数组计算各自的和, 然后计算出sum_a - sum_b, 然后开始LOOP, 找到能使sum_a与sum_b逼近的值, 交换.
直到没有交换为止.
s5unty 回复于：2006-11-13 15:43:33
在1/4炷香之后，我意识到如果a = {1,2,3}; b = {0,0,999}。那么先排序后交叉取就不行了:)
[ 本帖最后由 s5unty 于 2006-11-13 15:46 编辑 ]
yg 回复于：2006-11-13 17:00:59
可以不用穷举，递归、回溯都行啊
namtso 回复于：2006-11-13 17:16:41
我相信，这个题在8分钟内能写出代码来的人，绝对是大大的牛人。
我觉得应该这样：
a和b 分别求出累加和，得出累加和的差c1，然后循环查找找a中的某个元素a，使得a与b中的某个元素b[j]交换之后，得出一个新的累加和之差c2，并且|c2|<|c1|，如果找到这样的一个元素a，则与b[j]交换，然后进入下一轮的递归运算。如果找不到这样的一个元素，则说明此时两个数组的累加和之差已经最小。
mill888 回复于：2006-11-13 17:29:28
8分钟就能写出正确方法的人，建议就不要去华为了，应当去更好的公司。
招聘中，建议华为公司应当定好自己的位。
yuxh 回复于：2006-11-13 20:20:46
引用：原帖由 zhhui2000 于 2006-11-13 07:54 发表
先各自排序,再交叉存放较大无素
这个基本可行，但不是交叉存放较大元素，而是哪边的和小就一直放大元素，直到n，然后把剩下的扔到另一组中就ok了。
greensky_34 回复于：2006-11-13 20:25:06
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[j]交换之后，得出一个 ...
[ 本帖最后由 greensky_34 于 2006-11-13 20:29 编辑 ]
lebk 回复于：2006-11-13 21:36:31
我有个想法，利用天平的原理：
１．两端各有n个元素．其总重分别为：W1, W2,差为diff_w(W1,W2)
２．结束条件是，diff_w(W1,W2)小于等于左右两边中任意元素之差的最小值．
３．如果不满足上述条件则进行置换，置换的规则是，将上述两边任意二元素之差最接近diff(w1,w2)得元素进行置换．.再重复上述步骤．
windy2335 回复于：2006-11-13 21:43:37
引用：原帖由 hithotwinds 于 2006-11-13 10:16 发表
刚学编程两个月，不知道思路是否正确，错就一定有的。
#include"stdio.h"
com(int a[2000],int n)
{int i,j,p,q,s;
for(i=0;i<2*n-1;i++)
{
a[0]=q,p=i;
for(j=i+1;j<2*n;j++)
...
才两个月能写出这么长的程序还是不错滴。。。
加油！！
apzc2529 回复于：2006-11-13 22:14:12
引用：原帖由 ccjjhua 于 2006-11-13 11:42 发表
把a,b 2数组的元素放到数组3（2n大小） 中进行排序，
a 先取最小的，b先取次小的，
然后根据a,b已取元素和的大小来决定谁来取剩下元素中最小的。策略是，已取得的所有元素之和大的来取C中剩下元素中的最小者。如 ...
这种方法似乎很可行:D
s5unty 回复于：2006-11-13 22:32:04
我写了80分钟，未果
当时心想，TMD，难道这是google面试题吗
qqq112233g 回复于：2006-11-13 22:36:14
小弟觉得这个题目应用动态规化来解：
原问题与下问题应该属同类。
有一组数a1,a2,a3,...,an. 求出一个子串，其各元素的和总元素和的一半差值最小！设总元素和为sum，
子串和为s_sub. 差值为dis[j],表示第 i个元素到j 个元素之间的子串和。每个元素有两种状态，1为选，0为不选。
当 i==j 时 dis[j] = a = a[j]
当 i<j 时 dis = min{sum-s_sub-a, sum-s_sub}
这是大概思想，如有错误望请正！
s5unty 回复于：2006-11-13 22:43:10
引用：原帖由 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;
}
kongqiang 回复于：2006-11-13 23:12:14
>>有两个数组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 即所求的情况。
：）。
大概就是这样的，用循环，呵呵。
chouy 回复于：2006-11-14 00:06:54
1. 求和并除二, 记为 AVG
2. 用短的数组长度个的数字排列组合, 找最接近 AVG 的.
3. 把这几个数填入短数组, 其余填入长数组.
不知道这道题中是否要求输出换的步骤, 如果需要, 小 CASE. 不说了.
greensky_34 回复于：2006-11-14 00:28:40
引用：原帖由 s5unty 于 2006-11-13 22:43 发表
不行阿，我理解后用c实现，结果不正确，可能是我理解有问题？
#include <iostream>
using namespace std;
void change(int* a, int* b) {
int t = *b;
*a = t;
*b = * ...
完整的程序是这样的，可以参考一下
#include <stdio.h>
#include <math.h>
#define N 10
void ary_init(int a[], int b[]){ //初始化数组
int i;
for (i=0; i<N; i++){
a = rand()%100;
}
for (i=0; i<N; i++){
b = rand()%100;
}
return;
}
long sum(int a[]){ //数组求和
int i;
int s;
for (s=0,i=0; i<N; i++){
s += a;
}
return s;
}
void change(int *a, int *b){ //数组元素交换
int tmp;
tmp = *a;
*a = *b;
*b = tmp;
return;
}
void prt_ary(int a[], int b[]){ //列印两数组元素及各自元素和
int i;
for(i=0; i<N; i++){
printf("%5d ", a);
}
printf("\n");
for(i=0; i<N; i++){
printf("%5d ", b);
}
printf("\n");
printf("%d\n", sum(a));
printf("%d\n", sum(b));
}
int main(){
int i;
int j;
int a[N];
int b[N];
int a_sum;
int b_sum;
int tmp;
int ab_diff;
ary_init(a,b);//初始化
prt_ary(a, b);//列印当前数组状态
ab_diff = abs(sum(a)-sum(b));
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));
}
}
}
prt_ary(a, b);//列印交换后数组状态
getch();
}
[ 本帖最后由 greensky_34 于 2006-11-14 00:30 编辑 ]
小帅哥飞飞 回复于：2006-11-14 00:31:03
比如说总共加起来为数组：1，2，3，4，5，6
如果算6-5，4-3，2-1（12楼的算法），然后求和结果最小差是3
但我可以这样分组（1，6）一组，（2，5）一组，4，3分到两个组，结果最小差才是1
jinjianlee 回复于：2006-11-14 08:53:43
首先可以用穷举的方式来实现该方法
在此基础上再优化算法（即排除没有必要的计算），最后必然可以得到想要的结果
pinyin 回复于：2006-11-14 09:16:30
引用：原帖由 mill888 于 2006-11-13 17:29 发表
8分钟就能写出正确方法的人，建议就不要去华为了，应当去更好的公司。
招聘中，建议华为公司应当定好自己的位。
共鸣
天山峰右 回复于：2006-11-14 09:25:11
可以用背包算法
轮流取数、按差值取数都不能保证正确性
比如对于原始数组：
a[]={1,2,3}
b[]={4,10,20}
或者：
a[]={1,29,30}
b[]={50,90,100}
banboy 回复于：2006-11-14 09:32:01
首先看图片信息-------这个题不一定就能交叉，你们能确定交叉就对吗，不对的，这也是我刚开始错误的思路，哈哈
我很就没写程序了，我是个做网页的，现在也不知道用哪种语言表达了，希望写程序比较好的朋友，把程序写出来把，就一个函数，我认为就能解决这个问题，
你们的程序中只要不区分当N为奇数还是偶数的情况，你们的算法就是错误的，我可以这么肯定的说，
你们只需要看N的判断，就可以知道这个算法的正确还是错误，
我个人认为，写程序，未必一定要用，英语来表达，
这样会达不到让看的人明白的效果的，
呵呵，一个没编过程的人，不知道说的对不对，但是我看过LINUX 内核和STL，自认为比别人懂模式。
我确定这个绝对正确，我用了10分钟
然后，将a,b数组合并，成一个数组C，
排序C，
然后将C中的数组
这个时候要看N为奇数还是偶数了 ，分析如图
这样就应该可以了把，
例如；
C数组；123456
那么A，B将取如下图
[ 本帖最后由 banboy 于 2006-11-14 10:10 编辑 ]
billzhou 回复于：2006-11-14 09:35:18
这样一定不行
windy2335 回复于：2006-11-14 09:37:03
小弟想到一个算法，，大家给点意见
定义一个c[2N]数组，将A数组和B数组里面的元素都放到C数组中，然后对C数组小到大排序，排好后在取数，在定义一个的D[N]数组，将C的第一个加上C的第2N个放到D[0]中，C的第二个加上C的第2N-1个放到D[1]中。。。。放好后，再将D数组从小到大排序，在又按照上面的方法，第一个加上最后一个放到另一个数组的第一个中，第2个加到数第二个放到另一个数组的第2个中。。。以这中思路一直排下去，最后得到一个两个元素的数组，那这数组中的两个元素的差应该就是最小的了。。。
这个数组中的两个元素中的每一个都是由N个数加起来的，所以在一开始放数的时候要对这些数进行记录。。。得到后便可以将这2N个数分配给A数组和B数组了.....
这种方法应该是可行的。。。。高手指点下....
huntrsky 回复于：2006-11-14 09:37:46
greensky 的算法很不错啊~~~大家看看可否再优化！？
pywj777 回复于：2006-11-14 09:38:10
引用：
QUOTE:
原帖由 zhhui2000 于 2006-11-13 07:54 发表
先各自排序,再交叉存放较大无素
这个基本可行，但不是交叉存放较大元素，而是哪边的和小就一直放大元素，直到n，然后把剩下的扔到另一组中就ok了。
同意，但不应该是哪边小就一直放大元素，直到n， 应该是直到这个组元素的和大于另一组元素和时，再将下一元素放到令一组，若两组之和相等时，将下一元素放到元素最多的那个组，然后以同样的方法继续剩下元素的放置，直到有一个组为n，然后把剩下的放到另一个组。
banboy 回复于：2006-11-14 09:42:32
我想删除这个回复，我的完整回复在前面，我不知道但是删除不掉，
大家不要看这个了，
我上面有个回复，大家可以看一下了，
我很久没写代码了，都在做网页，你们把代码写下吧
[ 本帖最后由 banboy 于 2006-11-14 10:04 编辑 ]
splitflag 回复于：2006-11-14 09:58:20
楼上的，解释一下，为什么这么取？
cuicp 回复于：2006-11-14 09:58:49
大侠们看这样可不可以：
1。先把两个数组相加，求平均数（a）。
2。在数组中取出和平均数差最小的一个或多个，如果是一个就分在一组，如果是多个就平均分（奇数个和偶数个一样）。
3。把剩下的元素排序，一次取两个元素（升序或降序），算一下两个元素的和（b）与差（c），取（b－a）和（c－a）绝对值小的那个，如果（b－a）小，把两个元素都加到和小的那个组中去，如果（c－a）小，把b和c中大的那个加到元素和小的那一组，把b和c中小的那个加到数组和大的那一组。
例如：
1，3，5
平均数：3
取3，分为第一组，
取1，5,因为（（1＋5）－3） > （（5－1）－3）,把1分给和大的那组，也就是第一组，把5分给和小的那组，也就是第二组，因为其和为零。
这样，5－（1＋3）＝1
又例如：
1，5，10，15
平均数：7。75，
先取10，分为第一组，
然后取1，5，因为（7。75－（1＋5）） < （7。75－（5－1））,所以把1与5都分给数组和小的那组，也就是第二组，然后取15分给和小的那组，（因为只剩15了）
最后得到：（10＋1＋5）－15 ＝ 1
差最小。
类推：
1，2，3，4，5，6
分为：
3，1，2，5
4，6
差为：1
不知道这种分法怎么样？
大家参考一下！！
有不对的地方请高手指正！
谢谢！！
cuicp 回复于：2006-11-14 10:16:41
上面的算法又考略了一下，基本原则就是尽量趋近平均数，
但是在取的过程中是取两个还是取几个？什么情况是最优的？
是顺序取还是有别的方法？
也就是怎么算出剩下的元素取几个才能使最后的结果最接近平均数？
数学呀，真的好难！
高手指点！
谢谢！！
cMEr 回复于：2006-11-14 10:18:04
取出所有，大小排序，
最大减最小，
取最接近差值的元素，
放在较小的一组，
直到最后。
论证中。。。。
ccjjhua 回复于：2006-11-14 10:31:12
想想2个原始人，他们一起采集了一些土豆2n个，他们之前有一个协议，就是采集到的东西都要平分，最好他们会怎么分，会比较公平呢？土豆不进行切割。你拿一个，我拿一个，个数一样，要求分到的总重量差要最小。那他们应该先把所有的土豆按大小排序，某个人先拿最小的，另一个拿次小的放进自己的筐中。接着就是掂一下2个筐，觉得重些的那个人，先拿还没分掉的土豆中最小的。如此反复，直到土豆分完。
大家看看这个法子是不是最公平？
[ 本帖最后由 ccjjhua 于 2006-11-14 10:52 编辑 ]
cuicp 回复于：2006-11-14 10:34:11
引用：原帖由 cMEr 于 2006-11-14 10:18 发表
取出所有，大小排序，
最大减最小，
取最接近差值的元素，
放在较小的一组，
直到最后。
论证中。。。。
这样好像不行，
比如：
1，2，3，4，5，6
结果是不是：
3，5，1
4，2，6
可是不是最佳方案。
chzht001 回复于：2006-11-14 10:36:43
先将数组排序（全排序，两个数组一起排），然后类似如下处理
#include <iostream>
using namespace std;
void swap(int &x, int &y)
{
x = x ^ y;
y = y ^ x;
x = y ^ x;
}
int main()
{
int a[] = {1, 13, 34, 44, 54, 58};
int b[] = {3, 23, 45, 56, 67, 77};
int i, sub;
static int total = 0;
for(i = 5; i >=0 ; i--)
{
sub = b - a;
if(total)
{
if((total > 0 && sub > 0) || (total < 0 && sub < 0))
{
swap(a, b);
total -= sub;
}
else if((total >0 && sub < 0) || (total < 0 && sub > 0))
total += sub;
}
else
{
total = sub;
}
}
cout << "a: " << endl;
for(i = 0; i < 6; i++)
cout << a << " " ;
cout << endl;
cout << "b: " << endl;
for(i = 0; i < 6; i++)
cout << b << " " ;
cout << endl;
cout << "total: " << total << endl;
}
[ 本帖最后由 chzht001 于 2006-11-14 10:49 编辑 ]
btdm 回复于：2006-11-14 10:38:18
类似背包问题，用二叉树来表示，搜索一条从根到叶结点的权最小的路径，时间复杂度是2的n次方
cMEr 回复于：2006-11-14 10:57:48
引用：原帖由 cuicp 于 2006-11-14 10:34 发表
这样好像不行，
比如：
1，2，3，4，5，6
结果是不是：
3，5，1
4，2，6
可是不是最佳方案。
相等时让原最小一组成为最大，不知可行吗？
1,4,7,8,9,11,18,19
1,18,11,7
19,9,8,4
chzht001 回复于：2006-11-14 11:05:26
引用：原帖由 cMEr 于 2006-11-14 10:57 发表
相等时让原最小一组成为最大，不知可行吗？
1,4,7,8,9,11,18,19
1,18,11,7
19,9,8,4
那是因为还没有全排序，全排序时再结合我的处理方法才能得出结果
两数组和之差最小不一定是零，因为有两数组的数个数相同的约束
正确的处理应是先找出最大的和第二大的分别放入两个数组，然后再找除去这两个后的最大的和第二大的，再依据前一次
的差值确定第二次取的最大和第二大的数放进哪一个数组，依次类推
[ 本帖最后由 chzht001 于 2006-11-14 11:13 编辑 ]
emacsnw 回复于：2006-11-14 11:22:30
引用：原帖由 chzht001 于 2006-11-13 19:05 发表
那是因为还没有全排序，全排序时再结合我的处理方法才能得出结果
两数组和之差最小不一定是零，因为有两数组的数个数相同的约束
正确的处理应是先找出最大的和第二大的分别放入两个数组，然后再找除去这两 ...
这样是不对的，比如最大的元素如果大到超过其他所有元素的和，那么显然它所在的那个数组其他的n-1个元素应该是所有2n个元素里面最小的。
aloneme_live 回复于：2006-11-14 11:25:57
引用：原帖由 chzht001 于 2006-11-14 11:05 发表
那是因为还没有全排序，全排序时再结合我的处理方法才能得出结果
两数组和之差最小不一定是零，因为有两数组的数个数相同的约束
正确的处理应是先找出最大的和第二大的分别放入两个数组，然后再找除去这两 ...
如果数组为：
999,0,1
2,3,0
按照你这个算法就会有问题，依次得到：
999,3
1, 2,
0，0
chzht001 回复于：2006-11-14 11:26:52
引用：原帖由 emacsnw 于 2006-11-14 11:22 发表
这样是不对的，比如最大的元素如果大到超过其他所有元素的和，那么显然它所在的那个数组其他的n-1个元素应该是所有2n个元素里面最小的。
这种情况是没考虑到
[ 本帖最后由 chzht001 于 2006-11-14 11:30 编辑 ]
splitflag 回复于：2006-11-14 11:30:43
引用：原帖由 yuxh 于 2006-11-13 20:20 发表
这个基本可行，但不是交叉存放较大元素，而是哪边的和小就一直放大元素，直到n，然后把剩下的扔到另一组中就ok了。
同意！
chzht001 回复于：2006-11-14 11:37:48
哎，:roll:
[ 本帖最后由 chzht001 于 2006-11-14 12:00 编辑 ]
aloneme_live 回复于：2006-11-14 11:48:05
大家提出的任何算法，首先能够证明是正确的吗？我估计大部分都是在猜测而已。
这个题仅仅是想出正确的算法都不止需要8分钟，还说要8分钟内写出代码，痴人做梦啊。
谁要是能8分钟内想出正确的算法，我估计他都可以进微软研究院了，至于华为，他就别去了，浪费人才。
所以，大家先别忙着写程序，把算法说出来供大家讨论讨论就行，这个才能达到学习的目的。
[ 本帖最后由 aloneme_live 于 2006-11-14 12:01 编辑 ]
cMEr 回复于：2006-11-14 11:50:38
follow
:em11:
flw2 回复于：2006-11-14 12:20:11
8分钟,我觉得这个能写出来就非常8错了.
naker 回复于：2006-11-14 12:36:29
不会是用人工神经网络来做吧，这样不用枚举，计算量为O(1),可8分钟写代码肯定没戏了。瞎说的，大家别拿臭鸡蛋砸我。
seaway 回复于：2006-11-14 12:47:27
t1＝a1的和＋a2的和；
结果数组＝空数组;
循环开始（所有的数组组合情况）
{
t2=绝对值（新数组a-新数组b）;
if( t2< t1)
{
t1=t2;
结果数组CLEAR（）；
结果数组ADD（t2）；
} else if(t2==t1)
{
结果数组ADD（t2）；
}
}
return 结果数组;
如果有完善的数据结构开发包。3分钟就够了。其中30秒用来考虑，2分用来写程序，30秒用来编译运行
seaway 回复于：2006-11-14 12:48:40
t1＝a1的和＋a2的和；
结果数组＝空数组;
循环开始（所有的数组组合情况）
{
t2=绝对值（新数组a-新数组b）;
if( t2< t1)
{
t1=t2;
结果数组CLEAR（）；
结果数组ADD（t2）；
} else if(t2==t1)
{
结果数组ADD（t2）；
}
}
return 结果数组;
如果有完善的数据结构开发包。3分钟就够了。其中30秒用来考虑，2分用来写程序，30秒用来编译运行
cuicp 回复于：2006-11-14 13:35:47
引用：原帖由 seaway 于 2006-11-14 12:48 发表
t1＝a1的和＋a2的和；
结果数组＝空数组;
循环开始（所有的数组组合情况）
{
t2=绝对值（新数组a-新数组b）;
if( t2< t1)
{
t1=t2;
结果数组CLEAR（）；
结果数组ADD（t2 ...
高，实在是高，
呵呵，把所有的组合都试一遍，差最小的组合记下来，
不就行了？
不过要麻烦一下计算机大哥了，
可以算一下一共有多少种组合，
如果两个数组元素和是n，那么全面覆盖的次数大概是：
n+n*(n-1)+n*(n-1)*(n-2)...
这个对不对？要怎么算呢？大学的课程都忘光了！
如果要短时间内完成的话，这可能是个好办法！
hiawen 回复于：2006-11-14 13:59:03
应该是将两个数组作为一个数组进行冒泡排序。
a[0],b[0],a[1],b[1],......
scott_jia 回复于：2006-11-14 14:11:15
引用：原帖由 sithui 于 2006-11-13 09:33 发表
先整体排序，再交叉取数
英雄所见略同。
cuicp 回复于：2006-11-14 14:17:34
引用：
n+n*(n-1)+n*(n-1)*(n-2)...
这个好像算错了，是不是要除个2？
排列组合，忘光了！
：）
chzht001 回复于：2006-11-14 14:19:07
引用：原帖由 seaway 于 2006-11-14 12:48 发表
t1＝a1的和＋a2的和；
结果数组＝空数组;
循环开始（所有的数组组合情况）
{
t2=绝对值（新数组a-新数组b）;
if( t2< t1)
{
t1=t2;
结果数组CLEAR（）；
结果数组ADD（t2 ...
你做的很快，但计算机恐怕要累死了 :lol:
dalianpansky 回复于：2006-11-14 14:26:29
[color=Red][font=黑体]方案1.将a、b两个数组合成一个数组c（无需排序），清空a、b两数组。任取c中一个数据i，然后在c中查找与i差值最小的j，i放入a中，就放入b中，然后在c中去掉i和j；再次在c中任取一个数据i，然后在c中查找与i差值最小的j，i放入b中，j放入a中。（即奇数次取在数组a中，偶数次取在数组b中）。（注，两个n相加一定为偶数）
方案2. 将a、b两个数组合成一个数组c（2n个数据，无需排序），将所有数据相加，然后除以2，值记为i，然后随意组合n个数据相加，取和最接近i的组合为a，余下为b[/font][/color]
[ 本帖最后由 dalianpansky 于 2006-11-14 15:01 编辑 ]
crazy_li 回复于：2006-11-14 14:38:30
引用：原帖由 greensky_34 于 2006-11-14 00:28 发表
完整的程序是这样的，可以参考一下
#include <stdio.h>
#include <math.h>
#define N 10
void ary_init(int a[], int b[]){ //初始化数组
int i;
for (i=0; i<N; i ...
经过简单的验证，发现greensky_34的算法是对的啊。大家不要想得太复杂了。
{1,2,3} {0,0,999}
{1,2,3,4,5,6} {7,8,9,10,11,12}
[ 本帖最后由 crazy_li 于 2006-11-14 14:39 编辑 ]
白色乌鸦 回复于：2006-11-14 14:44:32
可以先做好个大致差不多的，再进行微调
zlqian 回复于：2006-11-14 15:13:43
假设sum(a)>sum(b)
（1）选取a中第i个数，b中第j个数，满足ai-bj < sum(a)-sum(b)。交换ai和bj。
（2）重新计算sum(a)和sum(b)
（3）重复步骤1和2直到条件1不能再满足。
（4）输出a和b
mmx_craft 回复于：2006-11-14 15:18:07
以下思路如何， 先把a,b合成一个2n的数组C, 然后按照如下规则选取。
1. a[0] = c [2n-1], b[0] = c[2n-2]
2. 按照suma>sumb, 取剩下的最大的给b，最小的给a； 反之最大的给a，最小的给b。
程序如下：
#include <stdio.h>
#include <stdlib.h>
static int
intcompare(const void *p1, const void *p2)
{
int i = *((int *)p1);
int j = *((int *)p2);
if (i > j)
return (1);
if (i < j)
return (-1);
return (0);
}
int change(int *a, int *b, int size)
{
int *c = (int*) malloc(2*size);
int pos_a,pos_b,pos_c,pos_cend;
int sum_a,sum_b;
int i;
memcpy(c, a, sizeof(int)*size);
memcpy(c+size, b, sizeof(int)*size);
qsort((void *)c, 2*size, sizeof (int), intcompare);
pos_a=pos_b=pos_c=0;
pos_cend = 2*size-1;
a[pos_a++] = c[pos_cend--];
b[pos_b++] = c[pos_cend--];
sum_a = a[0];
sum_b = b[0];
while (pos_cend > pos_c ) {
if (sum_a > sum_b) {
a[pos_a++] = c[pos_c++];
b[pos_b++] = c[pos_cend--];
sum_a += a[pos_a-1];
sum_b += b[pos_b-1];
} else {
a[pos_a++] = c[pos_cend--];
b[pos_b++] = c[pos_c++];
sum_a += a[pos_a-1];
sum_b += b[pos_b-1];
}
}
}
int main (int argc, char **argv)
{
int a[6]= {1, 2, 3,4,5,6};
int b[6]= {7, 8, 9,10,11,12};
int i;
change(a,b,6);
printf("a=");
for(i=0; i <6; i++)
printf("%d,",a);
printf("\n");
printf("b=");
for(i=0; i< 6; i++)
printf("%d,", b);
printf("\n");
}
xmyth 回复于：2006-11-14 17:04:15
当前数组a和数组b的和之差为
A = sum(a) - sum(b)
a的第i个元素和b的第j个元素交换后，a和b的和之差为
A' = sum(a) - a + b[j] - （sum(b) - b[j] + a)
= sum(a) - sum(b) - 2 (a - b[j])
= A - 2 (a - b[j])
设x = a - b[j]
|A| - |A'| = |A| - |A-2x|
假设A > 0,
当x 在 (0,A)之间时，做这样的交换才能使得交换后的a和b的和之差变小，x越接近A/2效果越好,
如果找不到在(0,A)之间的x，则当前的a和b就是答案。
所以算法大概如下：
在a和b中寻找使得x在(0,A)之间并且最接近A/2的i和j，交换相应的i和j元素，重新计算A后，重复前面的步骤直至找不到(0,A)之间的x为止。
[ 本帖最后由 xmyth 于 2006-11-14 20:45 编辑 ]
flw2 回复于：2006-11-14 17:42:34
xmyth 快四年一贴啊.
你说的我看懂了
cuicp 回复于：2006-11-14 19:42:44
引用：原帖由 xmyth 于 2006-11-14 17:04 发表
当前数组a和数组b的和之差为
A = sum(a) - sum(b)
a的第i个元素和b的第j个元素交换后，a和b的和之差为
A' = sum(a) - a + b[j] - （sum(b) - b[j] + a)
= sum(a) - sum(b) - 2 (a - b[j]) ...
想法很好呀，又有数学证明，但是什么时候会
找不到（0,A）之间的x呢？
比如：
1，2，3，4，5，12
最佳方案好像是：
4，5，3
1，2，12
那么0<（3－2）<(15-12)
好像不行呀？
是不是要改进一下结束的条件？
我考虑的对不对？
高手看看！
谢谢！！
xmyth 回复于：2006-11-14 20:44:31
这个结束条件应该是没有问题的
在你说的这个例子里，已经满足了我所提出的结束条件
前面我假设了A>0 (如果A不大于0，对换一下就好了)
所以这里a = {1,2,12}; b = {4,5,3};
x=a-b[j]
所有的x应该都不能满足（0, 3)的条件了，所以满足结束条件了。
exir 回复于：2006-11-14 20:52:31
真的只有八分钟吗？字都打不完啊。
flw2 回复于：2006-11-14 20:58:29
引用：原帖由 xmyth 于 2006-11-14 20:44 发表
这个结束条件应该是没有问题的
在你说的这个例子里，已经满足了我所提出的结束条件
前面我假设了A>0 (如果A不大于0，对换一下就好了)
所以这里a = {1,2,12}; b = {4,5,3};
x=a-b[j]
所有的x ...
我一眼就感觉你那公式很可能是对的
这种类似的题很多的
比如100个红包，7个人分，怎么分才最均匀，是不是更头疼？
flw2 回复于：2006-11-14 21:08:59
:lol:
greensky_34 回复于：2006-11-14 21:18:23
用二重循环把a中的每个元素和b中的每个元素逐个“尝试交换”，
如果是差值变小就维持交换，否则就交换回去，也就是不交换，
每有一次交换，“尝试交换”的二重循环就重新从头开始，
直到没有任何交换使差值变小为止。
这种方法不是很简洁，但的确是可行的。
前边贴出代码的算法，有过一次交换后，循环没有从头开始，所以是错误的。例如a[1]和b[j]交换后，b中的元素改变了，不能再保证a[0]和b[ i ]交换不会使差值变小，这时循环必须从头开始。
#include <stdio.h>
#include <math.h>
#define N 10
void ary_init(int a[], int b[]){ //初始化数组
int i;
for (i=0; i<N; i++){
a = rand()%10000;
}
for (i=0; i<N; i++){
b = rand()%100;
}
return;
}
long sum(int a[]){ //数组求和
int i;
int s;
for (s=0,i=0; i<N; i++){
s += a;
}
return s;
}
void change(int *a, int *b){ //数组元素交换
int tmp;
tmp = *a;
*a = *b;
*b = tmp;
return;
}
void prt_ary(int a[], int b[]){ //列印两数组元素及各自元素和
int i;
for(i=0; i<N; i++){
printf("%5d ", a);
}
printf("\n");
for(i=0; i<N; i++){
printf("%5d ", b);
}
printf("\n");
printf("%d\n", sum(a));
printf("%d\n", sum(b));
}
int slove(int a[], int b[]){
int i;
int j;
int is_swap = 0;//是否修交换过数据标志
int ab_diff;
ab_diff = abs(sum(a)-sum(b));
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){//判断是否需要交换元素
is_swap = 1; //置位交换标志
ab_diff = abs(sum(a)-sum(b)); //更新差值
}
else{
change(b+j, a+i);//不交换
}
}
}
return is_swap;
}
int main(){
int a[N];
int b[N];
ary_init(a,b);//数组元素初始化
prt_ary(a, b);//列印当前数组状态
while (slove(a, b));//处理数组
prt_ary(a, b);//列印交换后数组状态
getch();
}
[ 本帖最后由 greensky_34 于 2006-11-14 21:20 编辑 ]
cuicp 回复于：2006-11-14 23:14:09
引用：原帖由 xmyth 于 2006-11-14 20:44 发表
这个结束条件应该是没有问题的
在你说的这个例子里，已经满足了我所提出的结束条件
前面我假设了A>0 (如果A不大于0，对换一下就好了)
所以这里a = {1,2,12}; b = {4,5,3};
x=a-b[j]
所有的x ...
哦，明白了，如果(sum(a) - sum(b)) > (a -b[j]) > 0的话，也就是数组a的和比数组b的和大，
而数组b中有比数组a中小的元素，如果把a和b[j]交换，就可以把数组a和数组b的差缩小，又因为
(sum(a) - sum(b)) > (a -b[j]) ，所以交换后不会出现sum(a) < sum(b)的情况。这样循环调整后，
当整体上sum(a) > sum(b))时，局部上（数组元素）无法交换了，也就是无法找到符合条件的x了。
呵呵，本人天生比较笨，要想一想才能明白！
谢谢xmyth的解释！
aero 回复于：2006-11-15 00:08:30
引用：原帖由 xmyth 于 2006-11-14 17:04 发表
当前数组a和数组b的和之差为
A = sum(a) - sum(b)
a的第i个元素和b的第j个元素交换后，a和b的和之差为
A' = sum(a) - a + b[j] - （sum(b) - b[j] + a)
= sum(a) - sum(b) - 2 (a - b[j]) ...
和我想得一样。
zwylinux 回复于：2006-11-15 00:25:14
引用：原帖由 forrestgang 于 2006-11-13 00:56 发表
有两个数组a,b，大小都为n,数组元素的值任意，无序；
要求：通过交换a,b中的元素，使数组a元素的和与数组b元素的和之间的差最小
我写的一段，不知道对不对
#include<stdio.h>
int
sumb (int m[], int x)
{
int i;
int sum = 0;
for (i = 0; i < x; i++)
sum += m[ i ];
return sum;
}
main ()
{
int min;
int tmp;
int i;
int j;
int this;
int
a[3] =
{
1, 3, 3};
int
b[3] =
{
3, -1,9};
for (i = 0; i < 3; i++)
for (j = 0; j < 3; j++)
{
this = sumb (a,3) - sumb (b,3);
if(i==0&&j==0)
{
if(this < 0)
this = this * (-1);
min=this;
}
if(this<0)this=this*(-1);
if (this < min)
min = this;
else
{
tmp = a[ i ];
a[ i ] = b[ j ];
b[ j ] = tmp;
}
}
printf ("Min=%d\n", min);
}
[ 本帖最后由 zwylinux 于 2006-11-15 00:46 编辑 ]
gnap 回复于：2006-11-15 01:13:18
我的想法：
求整体的平均值V；
然后两个数组连接，整体根据元素与平均值之差的绝对值排序；
然后从中间断开；
如果新引入一个2n的指针数组，效率会比较高。
seaway 回复于：2006-11-15 08:58:05
引用：原帖由 chzht001 于 2006-11-14 14:19 发表
你做的很快，但计算机恐怕要累死了 :lol:
这点计算量怎么可能吧计算机累死。你太小看现在的计算机计算能力了。
太过强调算法是中国程序员的毛病。
你可能花半个小时完成了一个相对比较好的程序，比我的程序快了一倍 （30秒）
一用用了30分30秒
我用了3分钟
就是说你让客户等待了30分30秒
而我让客户等待了3分钟，从这个角度，我更有机会争取到客户。
一般应用程序，都是将实现功能作为第一目的。当需要处理效率问题时候才去单独分析优化。前提是用户选择了你的程序之后。否则用户都没选择你的程序，你程序再好有个屁用
seaway 回复于：2006-11-15 09:02:47
引用：原帖由 seaway 于 2006-11-14 12:48 发表
t1＝a1的和＋a2的和；
结果数组＝空数组;
循环开始（所有的数组组合情况）
{
t2=绝对值（新数组a-新数组b）;
if( t2< t1)
{
t1=t2;
结果数组CLEAR（）；
结果数组ADD（t2 ...
而且我的程序非常容易阅读和理解。
容易阅读也是好的程序的特点。他更容易维护，不容易出错。
至少可以用我的程序来检验你那只有数学家才能看懂的代码是不是可靠。
flw 回复于：2006-11-15 09:12:00
引用：原帖由 seaway 于 2006-11-15 08:58 发表
这点计算量怎么可能吧计算机累死。你太小看现在的计算机计算能力了。
太过强调算法是中国程序员的毛病。
你可能花半个小时完成了一个相对比较好的程序，比我的程序快了一倍 （30秒）
一用用了30分30秒
我 ...
你说的一点儿也不错，我深有同感。
可是，我还是有两点要说：
1，本帖的前提应聘的是华为，网络设备对性能的要求大家都知道吧？
2，在你发贴之时，前面已经有两位网友表示过自己的高性能算法了——至少比你的性能高的不是一点半点，你为什么不参考一下他们的做法呢？埋头苦干难道不是中国程序员的通病吗？
seaway 回复于：2006-11-15 10:16:48
引用：原帖由 flw 于 2006-11-15 09:12 发表
你说的一点儿也不错，我深有同感。
可是，我还是有两点要说：
1，本帖的前提应聘的是华为，网络设备对性能的要求大家都知道吧？
2，在你发贴之时，前面已经有两位网友表示过自己的高性能算法了——至少比你的 ...
首先我同意你的观点，我并不认为我的答案有多好。
如果考官在给我题目同时给了我前面几位兄台的答案我肯定是照抄不误，并仔细学习其精妙的算法。
但是我起码按要求完成了题目，起码比把结果算错的朋友更有优势。
要保证8分钟完成任务。你必须要考虑的的一个因素就是时间。怎么能在8分钟内完成任务。
我不是天才，所以我采用了最一般的思维方式在指定的时间内完成了任务。
做事情首先明确目标：
目标1：完成题目
目标2：确保结果正确
目标3：全部时间8分钟
我拿到题目后首先考虑如何实现，30秒后发现，以我的才智8分钟不可能写出精妙的算法。
所以，我拿出保守方案，就是以达到题目为目标。
如果哪位可以在8分中吧上面三个目标全部达成。这个工作机会我让给他一点都不遗憾。
[ 本帖最后由 seaway 于 2006-11-15 10:40 编辑 ]
splitflag 回复于：2006-11-15 10:26:54
引用：原帖由 xmyth 于 2006-11-14 17:04 发表
当前数组a和数组b的和之差为
A = sum(a) - sum(b)
a的第i个元素和b的第j个元素交换后，a和b的和之差为
A' = sum(a) - a + b[j] - （sum(b) - b[j] + a)
= sum(a) - sum(b) - 2 (a - b[j]) ...
不错啊，有证明呢。
hawk2012 回复于：2006-11-15 10:56:24
假设数组a中的所有元素用a1, a2, a3, ..., an表示， 数组b中的为b1,b2,b3,...,bn表示。
那么令result = (a1 + a2 + a3+ ... + an) - (b1 + b2 + b3 + ... + bn)
= (a1 + a2 + a3+ ... + an) + (b1 + b2 + b3 + ... + bn) - 2(b1 + b2 + b3 + ... + bn)
令Sum = (a1 + a2 +... + an) + (b1 + b2 + b3 + ... + bn) 这里Sum是个恒定的值
所以 result = Sum - 2(b1 + b2 + b3 + ... + bn)
要使 result 为最小，只需要(b1 + b2 + b3 + ... + bn)为最大。
所以 把数组a 和 b , 放到数组c中，进行排序（可以使用快速排序方法），然后将c数组中的前n个元素放到a数组中，后n个元素放到b中。这样的a,b数组就是符合题目要求的数组了
laowolf 回复于：2006-11-15 11:01:38
楼上的......狂晕..........................
susesuse 回复于：2006-11-15 11:06:10
引用：原帖由 hawk2012 于 2006-11-15 10:56 发表
假设数组a中的所有元素用a1, a2, a3, ..., an表示， 数组b中的为b1,b2,b3,...,bn表示。
那么令result = (a1 + a2 + a3+ ... + an) - (b1 + b2 + b3 + ... + bn)
= (a1 + a2 + a3+ ... + an) ...
所以 result = Sum - 2(b1 + b2 + b3 + ... + bn)
要使 result 为最小，只需要(b1 + b2 + b3 + ... + bn)为最大。
呵呵，没有考虑Sum - 2(b1 + b2 + b3 + ... + bn)可能为负数？
hawk2012 回复于：2006-11-15 11:08:28
是的， 是这个题目出的有问题，应该说是a b数组和的差的绝对值最小才对，不然我的算法就是最小的。
susesuse 回复于：2006-11-15 11:11:17
引用：原帖由 hawk2012 于 2006-11-15 11:08 发表
是的， 是这个题目出的有问题，应该说是a b数组和的差的绝对值最小才对，不然我的算法就是最小的。
确实您的想法很有新意，一般人想不到，呵呵。
laowolf 回复于：2006-11-15 11:17:06
hawk2012的算法是正确滴?........................................你们肯定?
(b1 + b2 + b3 + ... + bn)为最大,那么结果就是最小的n个数减最大的n 个数,这样还能做出差最小..............................................................................................................?
hawk2012 回复于：2006-11-15 11:22:03
引用：原帖由 laowolf 于 2006-11-15 11:17 发表
hawk2012的算法是正确滴?........................................你们肯定?
(b1 + b2 + b3 + ... + bn)为最大,那么结果就是最小的n个数减最大的n 个数,这样还能做出差最小................................... ...
是负数，当然是最小的。取绝对值是最大。
laowolf 回复于：2006-11-15 11:22:53
呵呵无语了......
moyan80 回复于：2006-11-15 12:38:25
O2O2...惊呆菜鸟无数……
cMEr 回复于：2006-11-15 14:06:37
个人觉得 xmyth 的比较合理些
求得天人惊现，以正视听。
:em11:
dalianpansky 回复于：2006-11-15 14:13:54
为啥没人评论我的想法呢？唉！
x2 回复于：2006-11-15 15:36:41
如果要求a-b最小, 将a和b联合成一个数组， 然后从小到大排序不行吗？
cuinantrue 回复于：2006-11-15 15:43:01
引用：原帖由 mill888 于 2006-11-13 17:29 发表
8分钟就能写出正确方法的人，建议就不要去华为了，应当去更好的公司。
招聘中，建议华为公司应当定好自己的位。
华为一直都“定得好好”的...
华为有限两次打电话叫我去面试都是催我还债的口气。真让人恶心。
cuinantrue 回复于：2006-11-15 16:06:16
引用：原帖由 xmyth 于 2006-11-14 17:04 发表
当前数组a和数组b的和之差为
A = sum(a) - sum(b)
a的第i个元素和b的第j个元素交换后，a和b的和之差为
A' = sum(a) - a + b[j] - （sum(b) - b[j] + a)
= sum(a) - sum(b) - 2 (a - b[j]) ...
牛逼。这种从数学角度来讲述算法的思路非常严谨而且语言直白。受教了。
ngzyl 回复于：2006-11-15 16:27:00
for (i = 0; i < n; i++) {
for (j = 0; j < i; j++)
if (a < a[j]) {
tmp = a[j];
a = b[j];
b[j] = tmp;
}
sa += a;
sb += b;
}
equal = sa - sb;
zwylinux 回复于：2006-11-15 18:19:44
引用：原帖由 hawk2012 于 2006-11-15 11:08 发表
是的， 是这个题目出的有问题，应该说是a b数组和的差的绝对值最小才对，不然我的算法就是最小的。
我说是你的理解有问题，a和b两个数之间的差值就一定是a－b？应该说它们的差值不要存在负数。
就比如说我们之间的年龄差，这是一个正数，地球人都知道
[ 本帖最后由 zwylinux 于 2006-11-15 18:22 编辑 ]
zwylinux 回复于：2006-11-15 20:14:04
上面我有发表我的算法，但是有些错误没改过来，现在这个是改进的，应该没什么问题了
#include<stdio.h>
#define SIZE 3
int
sumb (int m[], int n)
{
int i;
int sum = 0;
for (i = 0; i < n; i++)
sum += m[ i ];
return sum;
}
main ()
{
int min;
int tmp;
int i;
int j;
int this;
int a[SIZE] = {
1, 7, 3
};
int b[SIZE] = {
10, 15, 4
};
min = sumb (a, SIZE) - sumb (b, SIZE);
min = min > 0 ? min : (-1) * min;//初始化min，此时min为两个数组总和之差
for (i = 0; i < SIZE; i++)
for (j = 0; j < SIZE; j++)
{
this = sumb (a, SIZE) - sumb (b, SIZE) + 2 * (b[ j ] - a[ i ]);
this = this >= 0 ? this : (-1) * this;
if (this < min)//如果this不小于min的话就不进行交换
{
min = this;
if (min == 0)//如果找到差值为0的组合，则提前退出
break;
tmp = a[ i ];
a[ i ] = b[ j ];
b[ j ] = tmp;
}
}
printf ("Min=%d\n", min);
}
东方晨曦 回复于：2006-11-15 21:00:12
先放在用Temp组，放上2组数，然后相加，看看和除以2为多少，然后排序，从大的，开始交叉给数，到最后的时候，参考和除以2这个数，再用小值分配。
AiSa.C 回复于：2006-11-15 22:21:30
就不能定义个数字？？然后取a中与这个数字的差值，再取b中与这个数字的差值然后相加求最小值
kevert 回复于：2006-11-16 08:44:16
我的想法，先全部加起来求和然后除以2,然后从中找出离sum/2最小的和的数字存放在A数组中，剩下的放在B数组中。
kanwairen 回复于：2006-11-16 10:23:16
我晕.我不弄了
[ 本帖最后由 kanwairen 于 2006-11-16 10:36 编辑 ]
kernelxu 回复于：2006-11-16 17:13:53
引用：原帖由 kevert 于 2006-11-16 08:44 发表
我的想法，先全部加起来求和然后除以2,然后从中找出离sum/2最小的和的数字存放在A数组中，剩下的放在B数组中。
赞成这种方法:
suma = ave + Da
sumb = ave + Db
Da = -Db = (a - b) / 2
ave = (a + b) / 2
找一个数组，其元素之和最接近ave，找寻的方法可以采用回溯法吧
六零六 回复于：2006-11-16 17:24:32
好啊
chendreamy 回复于：2006-11-16 17:29:48
/*
问题： 有两个数组a,b，大小都为n,数组元素的值任意，无序。
要求： 通过交换a,b中的元素，使数组a元素的和与数组b元素的
和之间的差最小。
思路： 把a, b的数据合并到临时数组c，对c的数据按升序排序。
选择c里的一对最小数据分别放入a、b，再选择c里的一
对‘次’小数据。如果a的全部数据之和大于b的全部数
据之和，则：‘次’小两数据中，小的数据归入a，大的
归入b，反之小的数据归入b，大的归入a。依次类推。。。
*/
#include "stdafx.h"
#include <stdlib.h>
#include <stdio.h>
#include <conio.h>
#include <malloc.h>
#define MAX_SIZE 30
void sort(void * C, int size_c);
void split(int A[], int B[], int size_a, int size_b);
int main(int argc, char* argv[])
{
int i;
int A[MAX_SIZE], B[MAX_SIZE];
printf("\n\na[%d]=\n\n", MAX_SIZE);
for(i=0; i<=MAX_SIZE-1; i++)
{
A = rand() % 100;
printf("\t%d", A);
}
printf("\n\nb[%d]=\n\n", MAX_SIZE);
for(i=0; i<=MAX_SIZE-1; i++)
{
B = rand() % 100;
printf("\t%d", B);
}
split(A, B, sizeof(A)/sizeof(int), sizeof(B)/sizeof(int));
/* 打印a数组的最终结果 */
printf("\n\n\n\n\n\na[%d]=\n\n", MAX_SIZE);
for(i=0; i<=MAX_SIZE-1; i++)
printf("\t%d", A);
/* 打印b数组的最终结果 */
printf("\n\nb[%d]=\n\n", MAX_SIZE);
for(i=0; i<=MAX_SIZE-1; i++)
printf("\t%d", B);
getch();
return 0;
}
/*a, b为待交换数据的数组，size_a为a的长度，size_b为b的长度*/
void split(int A[], int B[], int size_a, int size_b){
int i;
int sum_a = 0, sum_b = 0;
int *C = (int*)malloc( (size_a+size_b)*sizeof(int) );
for(i = 0; i <= size_a; i++)
*(C+i) = A;
for(i = 0; i <= size_b; i++)
*(C+size_a+i) = B;
sort(C, size_a+size_b);
for(i = 0; i < (size_a+size_b)/2; i++)
{
A = sum_a > sum_b?C[i*2]:C[i*2+1];
B = sum_a > sum_b?C[i*2+1]:C[i*2];
sum_a+=A;
sum_b+=B;
}
}
/*冒泡法升序排序，c为待排序临时数组，size_c为c的长度 */
void sort(void * C, int size_c){
int i, j, t;
for(i=size_c; i>0; i--)
for(j=0; j<i-1; j++)
if( *((int*)C+j) > *((int*)C+j+1) )
{
t = *((int*)C+j+1);
*((int*)C+j+1) = *((int*)C+j);
*((int*)C+j) = t;
}
}
kernelxu 回复于：2006-11-16 18:01:43
引用：原帖由 chendreamy 于 2006-11-16 17:29 发表
问题： 有两个数组a,b，大小都为n,数组元素的值任意，无序。
要求： 通过交换a,b中的元素，使数组a元素的和与数组b元素的
和之间的差最小。
思路： 把a, b的数据合并到临时数组c，对c的数据按升序排序。
选择c里的一对最小数据分别放入a、b，再选择c里的一
对‘次’小数据。如果a的全部数据之和大于b的全部数
据之和，则：‘次’小两数据中，小的数据归入a，大的
归入b，反之小的数据归入b，大的归入a。依次类推。。。
这个算法是错误的。
举一个例子：
a[3] = {14, 13 12};
b[3] = {11, 10, 1};
那么合并之后
c[6] = {14, 13, 12, 11, 10, 1};
按照你的算法组合应该是
a[3] = {1, 12, 14}
b[3] = {10, 11, 13}
suma = 27
sumb = 34
sub = 34 - 27 = 7
但是有另一种组合方式：
a[3] = {1, 13, 14}
b[3] = {10, 11, 12}
suma = 28
sumb = 33
sub = 33 - 28 = 5
这个才是组合后和之差最小的。
而且绝对保证suma或sumb是离sum/2（这里是61/2 = 30.5）最近的。。。
绿茶主演 回复于：2006-11-17 13:34:02
ccjjhua (贝壳) 的想法不错啊！
引用：原帖由 ccjjhua 于 2006-11-14 10:31 发表
想想2个原始人，他们一起采集了一些土豆2n个，他们之前有一个协议，就是采集到的东西都要平分，最好他们会怎么分，会比较公平呢？土豆不进行切割。你拿一个，我拿一个，个数一样，要求分到的总重量差要最小。那他 ...
:em02:
ccjjhua 回复于：2006-11-17 14:12:20
我的想法是错的，
我试图去证明，就证明不了，后来有了一个反例，可以证明我的想法是错的。
如
a[3]={1 ,1 ,2};
b[3]={5 ,5 ,10};
对c 排序后c[6]={1，1，2，5，5，10}
可以知道把c分成2个和差最小的数组分别是
{1，1，10}和{2，5，5}，和差为0
可按我的算法，就应该是
{1，2，10}和{1，5，5}，和差是2，所以我的算法是错误。
绿茶主演 回复于：2006-11-17 14:25:40
噢，果然有问题，不过这办法还是挺好的，我想改一改就应该可以吧，让他们从大到小拿，谁的轻(或与另一个相等)要继续拿，否则换人拿，（如果有个人一直轻就一直拿下去，直到拿的数量为总数的二分之一时停止！）,这样就解决你的问题啦，嘿嘿，再找个反例出来试试!
[ 本帖最后由 绿茶主演 于 2006-11-17 14:28 编辑 ]
zhhui2000 回复于：2006-11-17 14:34:06
引用：原帖由 ccjjhua 于 2006-11-17 14:12 发表
我的想法是错的，
我试图去证明，就证明不了，后来有了一个反例，可以证明我的想法是错的。
如
a[3]={1 ,1 ,2};
b[3]={5 ,5 ,10};
对c 排序后c[6]={1，1，2，5，5，10}
可以知道把c分成2个和差最小的数组 ...
将你的算法稍改一下,如何:
1\排序
2\各自取最大,和小者优先;
3\和相等时,已取个数多者占先;
ccjjhua 回复于：2006-11-17 15:13:55
c[6]={10，8，0，6，6，6}
a[3]={10,8,0},sum(a)=18
b[3]={6,6,6},sum(b)=18
和差为0
按从大向小拿一样存在这样的问题。
a[3]={10,6,0},sum(a)=16
b[3]={8,6,6},sum(b)=18.
和差为2。
也就是说，我们错在凭什么要最大或最小的2个要分开，不能在同一个数组里。所以，这个法子是不可行的。
看来xmyth 兄的解法是唯一的正解了。
shanan 回复于：2006-11-17 15:24:40
题目没问题吗?
zwylinux 回复于：2006-11-17 16:20:12
引用：原帖由 zwylinux 于 2006-11-15 20:14 发表
上面我有发表我的算法，但是有些错误没改过来，现在这个是改进的，应该没什么问题了
#include<stdio.h>
#define SIZE 3
int
sumb (int m[], int n)
{
int i;
int sum = 0;
for (i = 0; i < ...
我的算法怎么没人回应一下啊。如果有错大家指出我也可以改正啊
lih928 回复于：2006-11-17 16:39:10
原我犯了很多数人一样的错误
主观一定认为最大的两个数一定要分开
[ 本帖最后由 lih928 于 2006-11-17 16:46 编辑 ]
tyc611 回复于：2006-11-17 17:34:47
原帖由 xmyth 于 2006-11-14 17:04 发表
当前数组a和数组b的和之差为
A = sum(a) - sum(b)
a的第i个元素和b的第j个元素交换后，a和b的和之差为
A' = sum(a) - a + b[j] - (sum(b) - b[j] + a)
= sum(a) - sum(b) - 2 (a - b[j]) ...
引用：
[color=Red]当x 在 (0,A)之间时，做这样的交换才能使得交换后的a和b的和之差变小，x越接近A/2效果越好, 如果找不到在(0,A)之间的x，则当前的a和b就是答案。[/color]
当这样的X不存在时，并不能结束算法。还可能存在如下情形，可以得到更小的差值：
例如： A=｛3， 5， 6， 7， 13， 14｝
B=｛1， 3， 7， 8， 10， 17｝
此时有，sum(A) - sum(B) = 2 ，并且不存在（0， 2）之间的x值。
但将A中的5和6与B中的3和7同时交换，得到
A=｛3， 3， 7， 7， 13， 14｝
B=｛1， 5， 6， 8， 10， 17｝
此时有：sum(A) - sum(B) = 0，此时的数组才是解。
我觉得这个算法难在如何有效寻找a(i)]和b[j]上
[ 本帖最后由 tyc611 于 2006-11-17 23:54 编辑 ]
tyc611 回复于：2006-11-17 17:38:02
>为啥上边的回复后部分斜了呢
知道了，原来是a中的在作祟:em02:
[ 本帖最后由 tyc611 于 2006-11-17 23:58 编辑 ]
天狼星 回复于：2006-11-17 18:19:04
建2各数组,把那些数从大到小,分别放入数组就成把. 放的时候判断一下就行了.
if (sum(a)>sunm(b))
a.push_back(num)
else
b.push_back(num)
dourt 回复于：2006-11-17 19:07:49
xmyth 兄从事什么专业?
能够快速的把实际问题模式化,并行成正确的数学思维,论证严谨.
而且整个模型具有智能的味道,佩服佩服
令我收益非浅那~~:em05:
svenwang 回复于：2006-11-17 23:27:05
int abs(int n)
{
return n >= 0 ? n : -n;
}
int sum(int *array, int count)
{
int sum = 0;
for (int i = 0; i < count; i++)
sum += array;
return sum;
}
void exchange(int *array1, int *array2, int count)
{
int sum1 = sum(array1, count);
int sum2 = sum(array2, count);
if (sum1 == sum2)
return;
int diff = abs(sum1 - sum2);
for (int i = 0; i < count; i++) {
for (int j = 0; j < count; j++) {
int s1 = sum1 + array2[j] - array1;
int s2 = sum2 + array1 - array2[j];
if (abs(s1 - s2) < diff) {
int tmp = array1;
array1 = array2[j];
array2[j] = tmp;
sum1 = s1;
sum2 = s2;
diff = abs(sum1 - sum2);
if (diff == 0)
return;
}
}
}
}
[ 本帖最后由 svenwang 于 2006-11-17 23:41 编辑 ]
slsl8460 回复于：2006-11-18 11:09:53
先把数据放到一个临时数组中，排序且求和sum；用背包算法，尽量是一个数组大小为n的存放的数字和为sum／2
emacsnw 回复于：2006-11-18 11:19:02
引用：原帖由 slsl8460 于 2006-11-17 19:09 发表
先把数据放到一个临时数组中，排序且求和sum；用背包算法，尽量是一个数组大小为n的存放的数字和为sum／2
原题说了数组里面元素的值任意，背包算法的效率线性于最大容积K，这里就是sum/2，如果这个数字可以任意，那背包算法也没什么意义了。
海滨 回复于：2006-11-18 17:53:17
关注．．．．
geba168 回复于：2006-11-18 22:21:21
搞一个数组C 包含了全部a b 的数据 并排序（再生成C的时候就排序）
然后在C里面 选1个 放到A 第2n个放到B 第2个放到A 第2n-1个放到B。。。。。。。
[ 本帖最后由 geba168 于 2006-11-18 22:23 编辑 ]
dark_ql 回复于：2006-11-18 23:36:03
int dist = 0;
int temp = 0;
for( int i=0; i<N; i++){
if( abs(dist+A-B) < abs(dist+B-A) ){
dist += A-B;
}else{
change(A,B);
dist += A-B;
}
}
说明：上述程序的目标是使交换后A数组的和减去B数组的和的绝对值最小，也就是两者之间相差最少
最终dist保存的即为两者之间的差
我就写了个例子验证了一下上述程序
A： 2 4 5 8
B： 1 7 6 9
按照上述规则，交换5-6，8-9，最终dist==0
如有错误请大家指出
[ 本帖最后由 dark_ql 于 2006-11-18 23:59 编辑 ]
svenwang 回复于：2006-11-19 00:00:36
这个帖子有点无聊了。很多人都只看第一贴，自己重复了别人的错误还不知道。
要是说是微软面试题估计更火爆。
erduo100 回复于：2006-11-19 10:24:52
没想出好的算法 我的思路把2n个数放在一个数组里 然后用组合找出n个数 求和 另n个数也求和 做查
求出所有这样的差值的最小值，故复杂度为theta（ C(2n, n)）再把原数组的值经过有限次的交换 调整成最优解的数组值就行了
其中C(2n, n)用的是回溯 构架是
void select_combination(int l, int p)
{
int i;
if (l == n)
{
。。。
return;
}
for(i=p; i<=2*n-(n-l); ++i) //上个位置填的是num[p-1]，本次从num[p]开始试探
{
b = true;
select_combination(l+1, i+1); //填下一个位置
b = false;
}
}
下面是整个程序
#include <stdio.h>
#include <math.h>
const int n = 3;
int num[2*n];
bool b[2*n];
bool bc[2*n];
bool first = true;
int de, sumae, sumbe;
int mins;
void copy(bool p[], bool q[], int n)
{
for (int i = 0; i < n; ++i)
{
q = p;
}
}
void select_combination(int l, int p)
{
int i;
if (l == n)
{
int suma = 0, sumb = 0;
for (i=0; i<2*n; ++i)
{
if (b)
suma += num;
else
sumb += num;
}
if (first)
{
first = false;
mins = abs(suma - sumb);
de = mins;
sumae = suma;
sumbe = sumb;
}
else
{
int d = abs(suma - sumb);
if (d < mins)
{
mins = d;
copy(b, bc, 2*n);
de = mins;
sumae = suma;
sumbe = sumb;
}
}
return;
}
for(i=p; i<=2*n-(n-l); ++i) //上个位置填的是num[p-1]，本次从num[p]开始试探
{
b = true;
select_combination(l+1, i+1); //填下一个位置
b = false;
}
}
bool find(int a[], int n, int va, int& pos)
{
for (int i = 0; i < n; ++i)
{
if (va == a)
{
pos = i;
return true;
}
}
return false;
}
void swap(int& a, int& b)
{
int tem = a;
a = b;
b = tem;
}
int main()
{
int a[n] = {1,4, 7};
int c[n] = {2,5,12};
int i, suma = 0, sumc = 0;
for (i = 0; i < 2*n; ++i)
{
if (i < n)
{
num = a;
suma += a;
}
else
{
num = c[i-n];
sumc += c[i-n];
}
b = false;
}
select_combination(0, 0);
// 下面是追踪交换的顺序
int ac[n], cc[n], p = 0, q = 0;
for (i = 0; i < 2*n; ++i)
{
if (bc)
ac[p++] = num;
else
cc[q++] = num;
}
p = 0;
int pos;
// 使a中的值与ac中的值相同
while (p < n)
{
if (a[p] == ac[p])
{
++p;
continue;
}
else
{
if (find(c, n, ac[p], pos))
{
printf("swap %d in a[%d] and %d in c[%d]\n",
a[p], p, c[pos], pos);
swap(a[p], c[pos]);
}
// a[p] 一定在数组a里 需交换3次
else
{
find(a, n, ac[p], pos);
printf("swap %d in a[%d] and %d in c[%d]\n",
a[p], p, c[0], 0);
swap(a[p], c[0]);
printf("swap %d in a[%d] and %d in c[%d]\n",
a[pos], pos, c[0], 0);
swap(a[pos], c[0]);
printf("swap %d in a[%d] and %d in c[%d]\n",
a[p], p, c[0], 0);
swap(a[p], c[0]);
}
}
++p;
}
// 使c中的值与cc中的值相同
q = 0;
while (q < n)
{
if (c[q] == cc[q])
{
++q;
continue;
}
else
{
find(c, n, cc[q], pos);
printf("swap %d in c[%d] and %d in a[%d]\n",
c[q], q, a[0], 0);
swap(c[q], a[0]);
printf("swap %d in c[%d] and %d in a[%d]\n",
c[pos], pos, a[0], 0);
swap(c[pos], a[0]);
printf("swap %d in c[%d] and %d in a[%d]\n",
c[q], q, a[0], 0);
swap(c[p], a[0]);
}
++q;
}
printf("\n交换前suma: %d, sumb: %d\n", suma, sumc);
printf("交换后suma: %d, sumb: %d\n", sumae, sumbe);
return 0;
}
wswn5456 回复于：2006-11-20 02:17:24
引用：原帖由 mike_chen 于 2006-11-13 09:34 发表
放到一个临时数组里排序后，两头取，分别存在a,b里
我同意这个
lknh17 回复于：2006-11-20 06:27:04
你们还在讨论这个问题呢...题说交换，又没说要给出交换的过程。。所以完整程序很简单......变个思维想想么
呵呵
lknh17 回复于：2006-11-20 06:39:16
另外，xmyth 的算法是基于贪心的，所以并不是最优的，只不过大多时候是最优的而已
lknh17 回复于：2006-11-20 06:44:03
再罗嗦点.....认清此题问题本是NP问题，就不会去想一些自以为很好的算法了
老老实实回朔剪枝吧，此题剪枝才是优化的王道，目前我用了3处剪枝已经将速度加速了很多
比较遗憾的是题目没给n范围，所以不好考虑剪枝的代价，所以我认为不给出n的规模此题写起来没什么意义，
所以代码也就不贴了。。。。
tank1111 回复于：2006-11-20 13:01:53
参加tyc611 的帖子
发现xmyth算法的模型还是有问题，如tyc611的例子，同时交换不能只限于一个元素
我的想法：
也许可以拓展成只要找到x在(0, A], 合集，不是开集，就进行交换
例子如下：
3,5,6,7,13,14 sum = 48
1,3,7,8,10,17 sum = 46
因为a[1] - b[1] = 2, 在(0, 2]之间, 且没有更逼近于A/2的选择，故交换之
3,3,7,8,10,17 sum = 48
1,5,6,7,13,14 sum = 46
现在a[3] - b[3] = 1, 在(0,2]之间， 交换
3,3,6,8,10,17 sum = 47
1,5,7,7,13,14 sum = 47
得到最佳结果
xmyth 回复于：2006-11-20 16:56:27
我前面提出的算法的确是错误的，贪婪算法在这种情况下不可行。
而楼上的想法也是错误的，比如这个简单的例子就行不通了
a = {11,12,8,91}
b = {1,2,17,100}
动态规划算法对这个题目应该是适用的
该题等价于在2n中元素中选取n个元素，使得这n个元素的和最接近于2n个元素总和的一半
/*
* 在数组c中的n个元素中选取m个元素，使得这m个元素的和最接近y
* func(c, n, m, y) 就表示这m个元素的和
* 然后通过比较func(c, n, m, y) 和 func(c + 1, n - 1, m, y) 就可以确定选取的这m个元素是哪几个
*/
func(int *c, int n, int m, int y) {
if (m == 0)
return 0;
if (n == m)
return sum(c, n);
a = func(c + 1, n - 1, m, y);
b = func(c + 1, n - 1, m - 1, y - *c) + *c;
return abs(y - a) <= abs(y - b) ? a:b;
}
[ 本帖最后由 xmyth 于 2006-11-21 21:01 编辑 ]
新新手 回复于：2006-11-20 18:36:57
设2n个数的和为S， 平均数为A， 最终挑选的n个数字和为S1， 两组数的差为D， 则
|S1 - （S - S1 )| = |2S1 - 2nA| = D
由上可知，如果D最小，S1必定最接近nA，
设数组C，2n个数与A的差。于是题目变成从数组C中挑选n个元素，使其和最接近0。
依次选最接近0 的元素Ci，
这不是最后的结果，但是以后的优化我不知道怎么做，请高手指教。
hgmyjr 回复于：2006-11-21 16:46:54
既然是最小肯定包括差值为负数.所以可以搜索两个数组到临时数组中[2n],然后排序小端放入A,大端放入B.
xzw077 回复于：2006-11-21 17:03:09
没有简单的方法 应该会用到背包算法。8分钟 呵呵 你去叫F1
的兄弟出来做做看有几个人能搞定：）
epegasus 回复于：2006-11-21 18:44:18
都这么久了早被华为淘汰了
lknh17 回复于：2006-11-22 18:54:03
哈哈，不过这是在哪面试的，华为来我们学校似乎不出什么现场编程的题
而且华为工资不知道怎么给的，看学校BBS上，同是本科生有的3K，有5.5K，很怪啊
mu_mu8309 回复于：2006-11-23 13:27:09
我个人认为是对两个数组分别排序,然后计算每个数组的和,那数组的和大的数组的小的数和数组的和小的数组的 大的数交换,比如数组A的和比数组B的和大,就那B中的小数和A中的大数交换,然后在比较,在交换.......
呵呵,可能说的还是不太清楚,我的表达能力不好:P
toplee 回复于：2006-11-23 15:21:30
从头到尾看了一遍，得到启发，不过至今楼主也没有公布正确结果，我也尝试搞了一个，考虑到数组处理和打印显示的方便，懒得用c来写这段代码，尝试用PHP来写了一段，经过各种测试案例没有发现失败。
代码如下：
<?php
//下面列举了三种前面常提到的特殊例子和一个通常情况下的数组例子，均进行了测试
$a = array(1,0,3);
$b = array(1,2,20);
$a = array(3,5,6,7,13,14);
$b = array(1,3,7,8,10,17);
$a = array(11,12,8,91);
$b = array(1,2,17,100);
$a = array(1,7,3,343,43,23,2323,454,5,5656,56,565,43,41,23,2,0,0,1);
$b = array(10,15,4,454,45,76,787,989,67,4545,65,566,2,343,3,4,2,4,0);
$count = count($a);
$c = array_merge($a,$b);
sort($c);
$sum = array_sum($c);
$max = $c[$count*2-1];
if ($max >= $sum/2) { //如果有一个数字大于其他数字总和，简单处理
for($i=0;$i<($count-1);$i++) {
$a[$i] = $c[$i];
$b[$i] = $c[$count-1+$i];
}
$a[$count-1] = $max;
$b[$count-1] = $c[$count*2-2];
} else { //通常情况
for ($i=0;$i<$count;$i++) {
$suma = array_sum($a);
$sumb = array_sum($b);
$x = ($suma - $sumb)/2; //两个数组各自和的差
$min = abs($x); //差的绝对值
$ch = false; //进行交换的开关
$t = 0;
for ($j=0;$j<$count;$j++) {
$y = ($a[$i] - $b[$j]); //两个元素间的差
$z = $x-$y; //数组和之差与元素差之间的差，不考虑正负
$absz = abs($z); //得到绝对值，用绝对值比较
if ($absz <= $min) {
$ch = true;
$min = $absz;
$t = $j;
}
}
if ($ch) { //找到$ai和$bj，进行交换
$tmp = $a[$i];
$a[$i] = $b[$t];
$b[$t] = $tmp;
}
}
}
sort($a);
sort($b);
//分别打印输出重新分组后的$a和$b数组，以及各自的和
echo "Sum(b) = ".array_sum($a)."\n";
print_r($a);
echo "Sum(b) = ".array_sum($b)."\n";
print_r($b);
?>
其实我的解题思路很简单：首先这道题可以认为是把2n个数进行均分成两组数，要求两组数的和尽可能接近。
从楼主的题目中可以看出，排序应该不是主要的，而如何进行交换是非常重要的，关键的就是ai和bj的确定问题。
这个里面可能会有两种情况，一种是所有的数字当中，有一个数字大于其他数字总和，这种情况很好处理，把2n个数字里面最小的0,n-2个加上最大的那个数字给a数组，剩下的为b数组即可，另外一种情况就是通常情况，没有一个数字绝对大。
[ 本帖最后由 toplee 于 2006-11-23 15:32 编辑 ]
agaonet 回复于：2006-11-28 01:58:26
引用：原帖由 la.lune 于 2006-11-13 10:55 发表
放到一个临时数组里排序后，两头取，分别存在a,b里
同意~
我也同意.
合并放到一个临时的数组里边,排序列.然后在分别交替取头尾.依次交替放往a,b数组.即:
取头,取尾.放往a.
取[头-1],取[尾-1].放b.
取[头-2],取[尾-2].放a.
取[头-3],取[尾-3].放b.
.........
这样永远A大于B..并且两数组之间最相等.
[ 本帖最后由 agaonet 于 2006-11-28 20:26 编辑 ]
chaiking 回复于：2006-11-29 14:56:35
我也想一个，
a) 两个数组合并c[n],然后从小到大排列，
b) 新建两个空数组， 第一大c[n]放在a[1],第二大c[n-1] 放在b[1]
c) 接下去就是递归了，c (i从后面开始)放在 min(a数组之和 ,b数组之和) 之中.
d) 结束
{1,2,3} {0,0,999}->{0,0,1,2,3,999}
a[1]=999,b[1]=3;
b[2] =2,
b[3]=1
b[4]=0;
b[5]=0;
chaiking 回复于：2006-11-29 16:11:03
// huawei.cpp : 定义控制台应用程序的入口点。
//某面试题，自己测试
/*
有两个数组a,b，大小都为n,数组元素的值任意，无序；
要求：通过交换a,b中的元素，使数组a元素的和与数组b元素的和之间的差最小
*/
#include "stdafx.h"
#include <iostream>
#include <vector>
#include <algorithm>
#include <functional>
using namespace std;
int min(vector<int> a1,vector<int> b1)
{
int sum1 = 0;
int sum2 = 0;
vector<int>::const_iterator Siter;
for(Siter = a1.begin(); Siter != a1.end(); ++Siter)
sum1 += *Siter;
for(Siter = b1.begin(); Siter != b1.end(); ++Siter)
sum2 += *Siter;
if(sum1 < sum2) return 1;
else return 0;
}
int _tmain(int argc, _TCHAR* argv[])
{
int a[6] = {3,5,6,7,13,14};
int b[6] = {1,3,7,8,10,17};
vector<int> a1;
vector<int> b1;
vector<int> c1;
vector<int>::const_iterator iter;
int i;
for(i=0; i<6; i++)
c1.push_back(a);
for(i=0; i<6; i++)
c1.push_back(b);
sort( c1.begin( ), c1.end( ), greater<int>( ) );
for(iter = c1.begin(); iter != c1.end() ; ++iter)
cout<<*iter<<',';
iter = c1.begin();
a1.push_back(*iter);
b1.push_back(*(++iter));
for(; iter != c1.end(); ++iter)
{
if(min(a1,b1))
a1.push_back(*iter);
else b1.push_back(*iter);
}
cout<<"\na1 :\n ";
for(iter = a1.begin(); iter != a1.end(); ++iter)
cout<<*iter<<',';
cout<<"\nb1 :\n ";
for(iter = b1.begin(); iter != b1.end(); ++iter)
cout<<*iter<<',';
}
lnfxcf 回复于：2006-11-29 16:17:00
把所有的数取出来，按照从大小进行排列，放在数组c。
a和b分别由totalA totalB累计分别的和（初值为0）。
顺序从c之中取两个数，把较大的数放在total较小的数足里。
over
mynets 回复于：2006-11-30 10:40:11
If performance is not a key factor, this program's result is very precise. And you can use it to evaluate other algorithms.
#include <sys/types.h>
#include <unistd.h>
#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
#define N 3 /* array size */
#define MINNUM 1 /* array element range */
#define MAXNUM 20
int curminval = INT_MAX;
int saveda[N], savedb[N];
static int
computediff(int a[], int b[])
{
int suma = 0, sumb = 0;
int i;
for (i = 0; i < N; i++)
suma += a, sumb += b;
return abs(suma - sumb);
}
static void
swap(int *p1, int *p2)
{
if (p1 && p2) {
int tmp = *p1;
*p1 = *p2;
*p2 = tmp;
}
}
static void
saveab(int a[], int b[])
{
int i;
for (i = 0; i < N; i++)
saveda = a, savedb = b;
}
static void
tryit(int a[], int an, int b[], int bn)
{
int diff;
if ((diff = computediff(a, b)) < curminval) {
curminval = diff;
saveab(a, b);
}
if (an < N-1)
tryit(a, an+1, b, bn);
if (bn < N-1)
tryit(a, an, b, bn+1);
swap(&a[an], &b[bn]);
if ((diff = computediff(a, b)) < curminval) {
curminval = diff;
saveab(a, b);
}
if (an < N-1)
tryit(a, an+1, b, bn);
if (bn < N-1)
tryit(a, an, b, bn+1);
swap(&a[an], &b[bn]);
}
int
main()
{
int a[N], b[N];
int i;
srand((u_int)time(NULL));
for (i = 0; i < N; i++) {
a = (rand() % (MAXNUM - MINNUM)) + MINNUM;
b = (rand() % (MAXNUM - MINNUM)) + MINNUM;
}
printf("Original:\n");
for (i = 0; i < N; i++)
printf("%s%3d%s", (i == 0)?"a[]: ":"", a, (i < N-1)?" ":"\n");
for (i = 0; i < N; i++)
printf("%s%3d%s", (i == 0)?"b[]: ":"", b, (i < N-1)?" ":"\n");
tryit(a, 0, b, 0);
printf("Result(%d):\n", curminval);
for (i = 0; i < N; i++)
printf("%s%3d%s", (i == 0)?"a[]: ":"", saveda, (i < N-1)?" ":"\n");
for (i = 0; i < N; i++)
printf("%s%3d%s", (i == 0)?"b[]: ":"", savedb, (i < N-1)?" ":"\n");
exit(0);
}
引用：
Some executing outputs：
Original:
a[]: 14 10 4
b[]: 4 11 16
Result(1):
a[]: 14 11 4
b[]: 4 10 16
Original:
a[]: 5 10 17
b[]: 2 10 15
Result(1):
a[]: 5 10 15
b[]: 2 10 17
Original:
a[]: 4 12 15
b[]: 3 18 8
Result(0):
a[]: 4 18 8
b[]: 3 12 15
Original:
a[]: 13 7 2
b[]: 3 18 19
Result(4):
a[]: 13 18 2
b[]: 3 7 19
norlan 回复于：2007-01-13 13:51:13
/*
解法假设：
1、假设存在数组a[n],b[n],且Sum(a[n]) < Sum(b[n]);
2、假设在数组a[n]与b[n]中，不存在元素a,使Sum(a[n]) < Sum(b[n])，且Sum(a[n])的值比上次求和的值大，则数组Sum(a[n])与数组Sum(b[n])
的差值最小。
*/
算法：
Sum(数据类型 *p, int n)//数组n的求和函数；
Swap(数据类型 *a, int i, 数据类型 *b, int j)//a与b[j]交换的函数
int intSumA = 0;
int intSumB = 0;
if ( Sum(a[n]) < Sum(b[n] ) //初始比价两个数组的和的大小
{
for(i = 0; i < n; i++)
{
intSumA = Sum(a[n]);
intSumB = Sum(b[n]);
for (j = 0; j < n; j++)
{
if ( (intSumA - a + b[j] < intSumB + a - b[j] )
&& ( a < b[j])
)
{
Swap(a, i, b, j);
i = 0;
break;
}
}
}
}
else
{
//与条件为真时类似处理；
}
pring a[n], b[n];
Bangel 回复于：2007-01-16 13:34:12
引用：原帖由 ccjjhua 于 2006-11-13 11:42 发表
把a,b 2数组的元素放到数组3（2n大小） 中进行排序，
a 先取最小的，b先取次小的，
然后根据a,b已取元素和的大小来决定谁来取剩下元素中最小的。策略是，已取得的所有元素之和大的来取C中剩下元素中的最小者。如 ...
这个好像行得通。。。
gnu.linyou 回复于：2007-01-16 14:58:31
把两个数据放在一起
然后使用 组合 C(n, 2 * n);
把每一个组合得到的值 和 sum / 2 进行相减
数值最小的 组合 当作一个数组， 剩下的当作另一个数组
组合C的 编写，找现成的排列组合算法，STL里面有一个next_permutation组合算法
iwolcbao 回复于：2007-03-06 17:05:39
引用：原帖由 mynets 于 2006-11-30 10:40 发表
If performance is not a key factor, this program's result is very precise. And you can use it to evaluate other algorithms.
#include <sys/types.h>
#include <unistd.h>
#incl ...
同意这个算法，
贴子是否该有个结论了。
其实想有个最好的结果！
tuzhiwei123 回复于：2007-03-07 11:18:13
先把两个数组归并成一个数组，再排序，完成后再分割，数组下标为单的为一个数组，为双的为另一个数组，就OK了
dpsuffix 回复于：2007-03-07 13:17:13
#include <stdio.h>
int c[20];
int mcam(int *a,int *b)
{
if( *a > *b)
return 1;
else if( *a == *b)
return 0;
else
return -1;
}
int printarr(int *a,int size)
{
int i ;
for(i = 0;i < size;i++){
printf("%d,",*a);
a++;
}
printf("\n");
}
int a[] = {10,34,230,400,321,4233,2000,50,320,333};
int b[] = {23,7000,200,634,987,230,640,46,135,257};
int main(int argc,char **argv)
{
qsort(a,10,sizeof(int),mcam);
qsort(b,10,sizeof(int),mcam);
printarr(a,10);
printarr(b,10);
int loop = 1;
int suma,sumb;
int gap;
int max,temp;
int i,j;
int sub;
while(loop){
int chgi=-1,chgj=-1;
max = 0;
suma=sum(a,10);
sumb=sum(b,10);
gap = (suma-sumb)/2;
for(i=9;i>=0;i--){
for(j=0;j<10;j++){
sub = a - b[j];
if(gap > 0){
if(max <sub && sub <gap){
max = sub;
chgi = i;
chgj = j;
}
}else if(gap < 0){
if( max >sub && sub >gap){
max = sub;
chgi = i;
chgj = j;
&n |
|
