有两个数组a,b, 大小都是n,数组元素的值任意,无序. 要求:通过交换a b中的元素,使数组a元素的和与数组b元素的和之间的差最小

题目:有两个数组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;
}