首页 > 代码库 > 有两个数组a,b，大小都为n,；通过交换a,b中的元素，使sum(a)-sum(b)最小。
有两个数组a,b，大小都为n,；通过交换a,b中的元素，使sum(a)-sum(b)最小。
有两个数组a,b，大小都为n,数组元素的值任意整形数，无序；
要求：通过交换a,b中的元素，使数组a元素的和与数组b元素的和之间的差最小。
当前数组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为止。
int sum1,sum2,a; //分别表示 a[]的和 b[]的和 以及2者之差 int temp; bool dayu0; //和之差是否大于0 int pos1,pos2; //等待交换的a[i]和b[j]的下标 i j float minn; //最接近a/2的a[i]-b[j]值 bool have1 ; //是否能有解 while (1) { sum1 = 0; sum2 = 0; for (int i = 0 ; i < n;++i) //求两个数组的和 { sum1 += ar1[i]; sum2 += ar2[i]; } a = sum1 - sum2; //和之差 dayu0 = a>0?true:false; //和之差是大于0还是小于0 have1 = false; //是否能找到解 for (int i = 0 ; i < n;++i) //找最接近a/2的 a[i]-b[j] { for (int j = 0;j < n;++j) { temp = ar1[i] - ar2[j]; if ((dayu0&&temp > 0&&temp < a)||(!dayu0&&temp < 0 && temp > a)) //如果a[i]-b[j] 在(0,a)之间 (超出的就没有意义了) { if (have1&&abs(temp - a/2.0) < minn) //若比之前的a[i]-b[j]更接近a/2 则更新 { minn = abs(temp - a/2.0); pos1 = i; pos2 = j; } else { have1 = true; minn = abs(temp - a/2.0); pos1 = i; pos2 = j; } } } } if (!have1) //若找不到符合条件的a[i]-b[j]了 则结束 { break; } swap(ar1[pos1],ar2[pos2]); //交换a b中的元素 }
有两个数组a,b，大小都为n,；通过交换a,b中的元素，使sum(a)-sum(b)最小。
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。