1.就是每次在两个数组里面分别取出两个随机数，如果交换后能使二者差的绝对值减少，就交换；
2.当然，有可能只需交换一个数，所以我在两个数组里面分别加入了一个0
3.至于证明，我想可以用数学归纳法。
#include<iostream.h>
#include<stdlib.h>
#include<stdio.h>
int a[64],b[64];
int AS(int x)
{
	return x<0?-x:x;
}
void input(int &n,int a[],int &s)
{
	for(int i=s=0;i<n;i++)
	{
		cin>>a[i];
		s+=a[i];
	}
	a[n]=0;
	n++;
}
compare(const void *e1,const void *e2)
{
	return *(int *)e1-*(int *)e2;
}
void change(int i,int j)
{
	int t=a[i];
	a[i]=b[j];
	b[j]=t;
}
void main()
{
	int n,i1,i2,j1,j2,t,an,bn,sa,sb,d1,d2;
	cin>>n;
	an=n/2;
	bn=n-an;
	input(an,a,sa);
	input(bn,b,sb);
	qsort(a,an,sizeof(a[0]),compare);
	qsort(b,bn,sizeof(b[0]),compare);
	for(t=0;t<10000;t++)
	{
		i1=i2=rand()%an;
		while(i2==i1)i2=rand()%an;
		j1=j2=rand()%bn;
		while(j2==j1)j2=rand()%bn;
		if(((a[i1]==0)+(a[i2]==0)+(b[j1]==0)+(b[j2]==0))%2!=0)continue;

		d1=AS(sa-sb);
		d2=AS(sa-sb-(a[i1]+a[i2]-b[j1]-b[j2])*2);
		if(d1>d2)
		{
			sa-=(a[i1]+a[i2]-b[j1]-b[j2]);
			sb-=-(a[i1]+a[i2]-b[j1]-b[j2]);
			change(i1,j1);
			change(i2,j2);
		}
		
	}
	if(sa<=sb)cout<<sa<<' '<<sb<<endl;
	else cout<<sb<<' '<<sa<<endl;
}

• 为什么要找两个数交换呢？我找一个数交换为什么就WA？ (26) linmeng 2008-11-16 16:29:47
• Re:我用随机过的，我想这样应该正确 (29) spracle_hao 2009-05-16 21:02:02
• Re:我用随机过的，我想这样应该正确 (29) spracle_hao 2009-05-16 21:02:04