【題目敘述】https://zerojudge.tw/ShowProblem?problemid=e536
【解題想法】枚舉，complete search
- 題目要求找出兩個不同的數字，加起來的結果最接近目標數字(x)。
- 先把來源數字 (a[ ]) 由小到大排序，枚舉任兩個數字(a[i], a[j])，計算總和(sum = a[i] + a[j])，如果 |sum – x| 比目前的答案(ans)小，就更新答案。
- 由於 a[ ] 已經排序，如果搜尋至 sum > x 且 sum – x 比 |ans – x| 大，可停止搜尋。
#include <iostream>
#include <algorithm>
using namespace std;
int a[1005];
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
int n, m, x, Case = 1;
while (cin >> n){
if (n == 0) break;
for (int i = 0; i < n; i++){
cin >> a[i];
}
sort(a, a+n);
cout << "Case " << Case++ << ":\n";
cin >> m;
while (m--){
cin >> x;
int ans = a[0] + a[1];
int delta = abs(ans - x);
for (int i = 0; i < n; i++){
for (int j = i+1; j < n; j++){
if (abs(a[i] + a[j] - x) < delta){
ans = a[i] + a[j];
delta = abs(a[i] + a[j] - x);
} else if (a[i] + a[j] - x > delta){
break;
}
}
}
cout << "Closest sum to " << x << " is " << ans << ".\n";
}
}
return 0;
}