学步园

参考网址：http://blog.csdn.net/v_JULY_v/article/details/6126444 第32题

问题描述：

有两个序列a,b，大小都为n,序列元素的值任意整数，无序；
要求：通过交换a,b中的元素，使[序列a元素的和]与[序列b元素的和]之间的差最小

代码实现：

#include <cstdio>
#include <cstdlib>
#include <cmath>

void swapi(int *x, int *y);
int sum(int a[], int n);
int isXinA(int x, int A);
void process(int a[], int b[], int n);

int main()
{
	int a[] = {1, 2, 3, 29, 30};
	int b[] = {1, 210, 232, 12311, 12312};
	
	int n = 5;
	process(a, b, n);

	for (int i = 0; i < n; i++)
		printf("%d  ", a[i]);
	printf("\n");
	for (int i = 0; i < n; i++)
		printf("%d  ", b[i]);

	printf("\n%d\n", abs(sum(a, n)- sum(b, n)));

	system("pause");
	return 0;
}

void swapi(int *x, int *y)
{
	int temp = *x;
	*x = *y;
	*y = temp;
}

int sum(int a[], int n)
{
	int ret = 0;
	for (int i = 0; i < n; i++)
		ret += a[i];

	return ret;
}

int isXinA(int x, int A)
{
	if ((x>0 && x<A) || (x>A && x<0))
		return 0;

	return 1;
}

void process(int a[], int b[], int n)
{
	int sum_a = sum(a, n);
	int sum_b = sum(b, n);
	int A = sum_a - sum_b;
	float minValue = abs(a[0]-b[0] - A/2.0);
	int ii = 0, jj = 0;
	int flag = 0;

	if (A == 0)
		return;

	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < n; j++)
		{
			int x = a[i] - b[j];
			if (x == 0)
				continue;
			if (isXinA(x, A) == 0)
			{
				float temp = (float)abs(a[i]-b[j] - A/2.0);
				if (temp < minValue)
				{
					minValue = temp;
					ii = i;
					jj = j;
					flag = 1;
				}
			}
		}
	}

	if (flag == 1)
	{
		swapi(&a[ii], &b[jj]);
		process(a, b, n);			//继续求解
	}

}

//求解思路：
//当前数组a和数组b的和之差为
//A = sum(a) - sum(b)
//
//a的第i个元素和b的第j个元素交换后，a和b的和之差为
//A' = sum(a) - a[i] + b[j] - （sum(b) - b[j] + a[i])
//	 = sum(a) - sum(b) - 2 (a[i] - b[j])
//   = A - 2 (a[i] - b[j])
//
//设x = a[i] - 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为止。