题目:有两个数组a,b, 大小都是n,数组元素的值任意,无序. 要求:通过交换a b中的元素,使数组a元素的和与数组b元素的和之间的差最小
分析:
假设a中的元素之和是suma,b中的元素之和是sumb. 差是diff = suma - sumb.数组a中任意一个元素a[i]和b数组中的任意一个元素b[j],如果a[i]和b[j]交换后能让diff的绝对值变小,就交换a[i]和b[j],否则就寻找下一对a[i]和b[j],当所有的a[i]和所有的b[j]都不能满足让diff的绝对值变小时,就得到了我们想要的数组.如下:
伪代码
//假设交换后的差值是diff_after,则交换后
suma(交换后) = suma(交换前) - a[i] + b[j]
sumb(交换后) = sumb(交换前) - b[j] + a[i]
//两个等式相减可得:
diff_after = (suma (交换前) - sumb (交换前) ) - 2( a[i] - b[j])
= diff - 2(a[i] - b[j])
//交换后的绝对值小于交换前,也就是abs(diff_after) < abs(diff_before)
C代码
void exchange(int *a, int *b, int n, int diff_before){
for (int i = 0; i < n; i ++) {
for (int j = 0; j < n; j ++) {
int diff_after = diff_before - 2 * (a[i] - b[j]);
if (abs(diff_after) < abs(diff_before)) {
swop(&a[i],&b[j]);
exchange(a,b,n,diff_after);
return;
}
}
}
}
// 计算数组a - b的值
int diffa_b(int *a, int *b, int n){
// 计算a的和 b的和
int suma = 0;
int sumb = 0;
for (int i = 0; i < n; i ++) {
suma += a[i];
sumb += b[i];
}
// a b 和的差
return suma - sumb;
}
// 交换
void swop(int *x, int *y){
int z = *x;
*x = *y;
*y = z;
}
