題目:有兩個數(shù)組a,b, 大小都是n,數(shù)組元素的值任意,無序. 要求:通過交換a b中的元素,使數(shù)組a元素的和與數(shù)組b元素的和之間的差最小

分析:

假設(shè)a中的元素之和是suma,b中的元素之和是sumb. 差是diff = suma - sumb.數(shù)組a中任意一個元素a[i]和b數(shù)組中的任意一個元素b[j],如果a[i]和b[j]交換后能讓diff的絕對值變小,就交換a[i]和b[j],否則就尋找下一對a[i]和b[j],當(dāng)所有的a[i]和所有的b[j]都不能滿足讓diff的絕對值變小時,就得到了我們想要的數(shù)組.如下:

偽代碼

//假設(shè)交換后的差值是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;
            }
        }
    }
}

// 計算數(shù)組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;
}