UVa10487 - Closest Sums (二分搜尋 Binary Search)

題目大意

給你一個數列，再給你一個數字，請你告訴這個數字最靠近這個數列某兩個值相加之總和(不可使用同個位置的數字)

題目連結

重點觀念

• 思考要怎麼樣迅速查詢到最靠近的值

分析

基本上是水題，再透過二分搜尋的方式將答案找出。

先將數列中所有數字都先兩兩相加後，再用二分搜尋找出最靠近的數字。

注意：這裡要用 upper_bound 會比較好寫，他勢必會找到比題目要查詢的數字更大，因此我們upper_bound 找到的數值(定義num[x])，再往前一個 index，num[x-1]，一定會比查詢的數字還要小，接下來再拿這兩個數字去比較即可，輸出離查詢數字更近的。

注意一開始的邊界問題，因此一開始先設無限大即可。

心得

簡單的一道題，希望自己考場都寫會瞜

題目程式碼

會在下面放一些簡單註解，供大家學習時參考。

#include <iostream>
#include <bits/stdc++.h>
#define LOCAL
#define MAXN 1020
using namespace std;
int n, m, idx, ans, temp, kase=1;
int num[MAXN]; //放題目數列用
vector<int> sum; //放兩兩相加後的陣列

int main()
{
#ifdef LOCAL
    freopen("in1.txt", "r", stdin);
#endif // LOCAL
    while(cin >> n && n){
        sum.clear(); //清除上次的狀態，否則會干擾此次題目
        sum.push_back(-0x3f3f3f); //先放第一筆資料進去，並且是無限大才不會導致
        //upper_bound 找到 (index)0 時跟 (index)-1 比較的問題
        for(int i = 0; i < n; i++){ //輸入資料
            cin >> num[i]; 
            for(int j = i-1; j >= 0; j--) sum.push_back(num[i]+num[j]); 
            //類似於 bubble sort 的將值輸入進去，這樣就不會重複輸入兩個值以上
        }
        sort(sum.begin(), sum.end()); //排序，方便二分搜尋

        cout << "Case " << kase++ << ":\n"; 
        cin >> m; //輸入題目資訊
        for(int i = 0; i < m; i++){
            cin >> temp; 
            idx = upper_bound(sum.begin(), sum.end(), temp) - sum.begin(); 
            //找到離查詢的數值更大的數值，(定義t)
            int gap1 = abs(sum[idx] - temp); //差距 1，找查詢數與 t 的距離
            int gap2 = abs(sum[idx-1] - temp); //差距 1，找查詢數與 t 的上一個數值的距離
            //cout << sum[index] << ' ' << sum[index-1] << '\n';
            if(gap2 < gap1) cout << "Closest sum to " << temp << " is " << sum [idx-1] << ".\n";
            else cout << "Closest sum to " << temp << " is " << sum[idx] << ".\n";
            //誰的差距大，就用另外一個差距的 sum[idx] or sum[idx-1] 來輸出答案。
        }

    }

    return 0;
}