学步园

32.
有两个序列a,b，大小都为n,序列元素的值任意整数，无序；
要求：通过交换a,b 中的元素，使[序列a 元素的和]与[序列b 元素的和]之间的差最小。
例如:
var a=[100,99,98,1,2, 3];
var b=[1, 2, 3, 4,5,40];

题目来源:
微软等公司数据结构+算法面试100 题V0.1 版
http://topic.csdn.net/u/20101126/10/b4f12a00-6280-492f-b785-cb6835a63dc9.html

分析：

假设序列a，b中元素的和为sum_a和sum_b。假设aa和bb分别为序列a，b中的元素，则交换aa，bb后序列的和变为sum_a-aa+bb，sum_b+aa-bb；两序列的差为（sum_a-aa+bb）-（sum_b+aa-bb）=sum_a-sum_b-2*（aa-bb）；

所以可以扫描序列a，b中的元素，找到使abs（sum_a-sum_b-2*（aa-bb））最小的两个元素进行交换，重复此过程，直至两序列的差无法减小。

bool Swap2Balance(int *pa, int *pb, int n)
{
	int suma=0,sumb=0;
	for (int i=0;i<n;i++)
	{
		suma+=pa[i];
		sumb+=pb[i];
	}

	int diff=suma-sumb;
	while (diff!=0)
	{
		int besti=0,bestj=0;
		int bestchange=0;
		for(int i=0;i<n;i++)
			for (int j=0;j<n;j++)
			{
				int change=(pa[i]-pb[j]);
				//交换后差为(suma-pa[i]+pb[j])-(sumb+pa[i]-pb[j])=diff-2*change
				if (abs(diff-2*change)<abs(diff-2*bestchange))
				{
					bestchange=change;
					besti=i;
					bestj=j;
				}
			}

		if (bestchange==0)	//差不能再缩小
			return false;
		int temp=pa[besti];
		pa[besti]=pb[bestj];
		pb[bestj]=temp;

		suma-=bestchange;
		sumb+=bestchange;
		diff=suma-sumb;

	}
	return true;
}