现在的位置: 首页 > 综合 > 正文

交换两个数组的值,使其和的差值最小

2014年03月02日 ⁄ 综合 ⁄ 共 1499字 ⁄ 字号 评论关闭

求解思路:
   
当前数组a和数组b的和之差为
    A = sum(a) - sum(b)

    a的第i个元素和b的第j个元素交换后,ab的和之差为
    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)之间时,做这样的交换才能使得交换后的ab的和之差变小,

x
越接近A/2效果越好,
   
如果找不到在(0,A)之间的x,则当前的ab就是答案。

   
所以算法大概如下:

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

/////////////////////////////////////////
算法

1.
将两序列合并为一个序列,并排序,为序列Source

2.
拿出最大元素Big,次大的元素
Small

3.
在余下的序列S[:-2]进行平分,得到序列max
min

4.
Small加到max序列,将Big加大min序列,重新计算新序列和,和大的为max,小的为min


 

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

假设序列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;
}

抱歉!评论已关闭.