題目:有兩個(gè)數(shù)組a,b, 大小都是n,數(shù)組元素的值任意,無序. 要求:通過交換a b中的元素,使數(shù)組a元素的和與數(shù)組b元素的和之間的差最小
分析:
假設(shè)a中的元素之和是suma,b中的元素之和是sumb. 差是diff = suma - sumb.數(shù)組a中任意一個(gè)元素a[i]和b數(shù)組中的任意一個(gè)元素b[j],如果a[i]和b[j]交換后能讓diff的絕對(duì)值變小,就交換a[i]和b[j],否則就尋找下一對(duì)a[i]和b[j],當(dāng)所有的a[i]和所有的b[j]都不能滿足讓diff的絕對(duì)值變小時(shí),就得到了我們想要的數(shù)組.如下:
偽代碼
//假設(shè)交換后的差值是diff_after,則交換后
suma(交換后) = suma(交換前) - a[i] + b[j]
sumb(交換后) = sumb(交換前) - b[j] + a[i]
//兩個(gè)等式相減可得:
diff_after = (suma (交換前) - sumb (交換前) ) - 2( a[i] - b[j])
= diff - 2(a[i] - b[j])
//交換后的絕對(duì)值小于交換前,也就是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;
}
}
}
}
// 計(jì)算數(shù)組a - b的值
int diffa_b(int *a, int *b, int n){
// 計(jì)算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;
}
