前言

今天講解兩題相關題目，希望大家可以透過題目更加瞭解二分搜尋使用時機

TOJ 47 / PB magic spell

題目說明

簡單來說有多筆詢問，要找出詢問值是否存在，或是輸出小於詢問值的最大整數、大於詢問值的最小整數，並且數列大小最大到 ，詢問筆數最大

解題思路

可以發現能夠使用二分搜尋來解題，並且這一題可以使用 C++ 的內建函式 lower_bound、upper_bound 解題，以下是函式解釋

• lower_bound：找出「大於或等於」val的「最小值」的位置：
  • auto it = lower_bound(v.begin(), v.end(), val);
• upper_bound：找出「大於」val的「最小值」的位置：
  • auto it = upper_bound(v.begin(), v.end(), val);

所以可以透過兩函式找出符合題目要詢問的條件，切記，進行二分搜尋時皆要先排序資料

AC Code

#include <bits/stdc++.h>
using namespace std;
long long a[1000000 + 10];
int main(){
    long long n;
    cin >> n;
    for(int i = 0;i < n;i++){
        cin >> a[i];
    } 
    sort(a,a + n);
    long long t;
    cin >> t;
    while(t--){
        long long k;
        cin >> k;
        long long x1 = lower_bound(a,a + n,k) - a,x2 = upper_bound(a,a + n,k) - a;
        if(a[x1] == k){
            cout << k << "\n";
        }else{
            if(x1 - 1 >= 0){
                cout << a[x1 - 1] << " ";
            }else{
                cout << "no ";
            }
            if(x2 != n){
                cout << a[x2] << "\n";
            }else{
                cout << "no\n";
            }
        }
    }
return 0;
}

c575. APCS 2017-0304-4基地台

題目說明

有 個服務點與 個基地台，要求基地台的直徑至少要多少才可以完全覆蓋所有服務點

解題思路

試想，基地台可以放在任何地方，因此如果直接窮舉放置點非常不明智，因為一來基地台數量可能不少、二是可能的座標點太多，所以我們可以嘗試看看用二分搜的方式求解，因為答案只會是 ~ 距離最遠的兩服務區距離，所以首先要先將座標點排序，然後將左界設為 ，右界設為距離最遠的兩服務區距離，而要檢查是否為可行的直徑，就是將 個點當成測定直徑大小的區塊，測試看看數量是否小於等於 個，如果需要額外基地台，則代表此直徑不可行，然後依此規則反覆更新左右界，就可以找到最短直徑了

AC Code

#include <bits/stdc++.h>
using namespace std;
long long n,k,p[50100],Min,Max;
int binary_search(long long l,long long r,long long t){
    while(l != r){
        long long mid = (l + r) / 2,a = 0;
        for(long long i = 0,now = 0;i < n;){
            while(p[now] <= p[i] + mid && now < n){
                now++;
            }
            a++;
            i = now;
        }
        if(a > t){
            l = mid + 1;
        }else{
            r = mid;
        }
    }
    return l;
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    while(cin >> n >> k){
        for(int i = 0;i < n;i++){
            cin >> p[i];
        }
        sort(p,p + n);
        Min = 1;
        Max = (p[n - 1] - p[0]) / k + 1;
        cout << binary_search(Min,Max,k) << "\n";
    }
    return 0;
}

總結

這兩題有一題是簡單的二分搜，一題是利用單調性的性質解題，所以會發現如果題目有辦法確定左右界，且有辦法將確認的規則寫成函式，然後在畫成圖形時 軸變大 也會上升，也就是具有單調性，這樣就可以使用二分搜，知道這個性質之後，會發現其實很多題目都可以這樣解題，而這也是二分搜強大的地方