通过交换 a,b 中的元素,使[序列 a 元素的和]与[序列 b 元素的和]之间的差最小。

原创
2014/05/18 22:23
阅读数 1.9K

题目:

有两个序列 a,b,大小都为 n,序列元素的值任意整数,无序;

要求:

通过交换 a,b 中的元素,使[序列 a 元素的和]与[序列 b 元素的和]之间的差最小。

例如:
var a = [100,99,98,1,2, 3];
var b = [1, 2, 3, 4,5,40];

最后的结果为:
var a = [1,99,98,1,2,2];

var b = [100, 3,3,4,5,40];

分析:

最简单的方法应该就是暴力穷举

这里阐述在网上看到的另一种方法:

对于序列a和b,令A = sum(a) - sum(b)

分别用i,j遍历a,b序列,若a[i]和b[j]交换

则: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])

即就是:(a[i] - b[j])在(0,A)之间并且最接近A/2则序列a,b的差值最小

因此得到算法:

在a和b中寻找使得x在(0,A)之间并且最接近A/2的i和j,交换相应的i和j元素,重新计算A后,重复前面的步骤直至找不到(0,A)之间的x为止。

代码实现:

(GCC编译通过)

#include "stdio.h"
#include "stdlib.h"

void balanceArray(int a[],int b[],int n);
int sumArray(int a[],int n);

int main(void)
{
	int i;
	int a[5]={0,1,2,3,4},b[5]={5,6,7,8,9};
	balanceArray(a,b,5);
	
	for(i=0;i<5;i++)
		printf("%3d",a[i]);
	printf("\n");	
	for(i=0;i<5;i++)
		printf("%3d",b[i]);
		
	printf("\n");
	return 0;
}

void balanceArray(int a[],int b[],int n)
{
	int *p,*q;
	int i,j,itemDValue,sumDValue,tmp,flag=1;
	
	if(sumArray(a,n) < sumArray(b,n))
	{
		p = b;
		q = a;
	}
	
	while(flag)
	{
		flag=!flag;
		for(i=0;i<n;i++)
		{	
			for(j=0;j<n;j++)
			{
				itemDValue = p[i]-q[j];
				sumDValue = sumArray(p,n) - sumArray(q,n);
				if((itemDValue < sumDValue)&&(itemDValue > 0))
				{
					flag=!flag;
					tmp = p[i];
					p[i] = q[j];
					q[j] = tmp;
				}
			}
		}		
	}

}

int sumArray(int a[],int n)
{
	int i,count=0;	
	for(i=0;i<n;i++)
		count += a[i];
	return count;
}


展开阅读全文
加载中
点击引领话题📣 发布并加入讨论🔥
打赏
0 评论
5 收藏
0
分享
返回顶部
顶部