【C++】競程筆記（對答案二分搜）

程式碼範例參考：NTUCPC Guide，此筆記僅為個人學習用途。

例題：https://zerojudge.tw/ShowProblem?problemid=h084

暴力解：直接窮舉所有可能高度的 x，並且看海報寬度，遍歷木板高度選可以貼的地方，但是這樣時間複雜度會是 $O(n^2)$ ，木板高度可能高達 $10^9$ 。

具體程式碼寫法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
// 暴力破解法.cpp

#include <bits/stdc++.h>

using namespace std;

bool canPlacePosters(const vector<int>& h, const vector<int>& w, int x) {
    int n = h.size();
    int k = w.size();
    int i = 0; // 木板的 index
    int poster = 0;

    while (poster < k) {
        int needed = w[poster]; // 此張海報需要的寬度
        // 在 h[i] >= x 的條件下，找長度為 w[poster] 的連續區間
        int count = 0;
        while (i < n) {
            if (h[i] >= x) {
                count++;
                if (count == needed) {
                    i++; // 貼完這張後往下一格，避免重疊
                    break;
                }
            } else {
                count = 0;
            }
            i++;
        }

        if (count < needed) return false;
        poster++;
    }
    return true;
}

int main() {
    int n, k;
    cin >> n >> k;

    vector<int> h(n);
    for (int i = 0; i < n; ++i) cin >> h[i];

    vector<int> w(k);
    for (int i = 0; i < k; ++i) cin >> w[i];

    int maxHeight = *max_element(h.begin(), h.end());
    int ans = 0;

    for (int x = 1; x <= maxHeight; ++x) {
        if (canPlacePosters(h, w, x)) {
            ans = x;
        }
    }

    cout << ans;
    return 0;
}

那這題可以用二分搜去解，若要用就需要找出 $x$ 的單調性。

先回去想想枚舉 $x$ 的過程，如果是從 $1$ 開始往上枚舉的話，其實在遇到第一個貼不完的高度時，就可以停下來了，畢竟高度越高的時候，能貼的地方只會越來越少，因此在更高的高度，也是不可能貼完的。當高度越高，用上面的方法能貼的海報就會越來越少、當高度越低，能貼的海報就越來越多。

這樣一來，我們就有一個「藏起來的序列」，這個序列的第 $x$ 項就是貼在高度 $x$ 的時候，最多可以貼幾張海報，長度就是我們本來的枚舉上界 $C = 10^9$ 。而這個序列是非嚴格遞減的，我們的目標是找到最後一個 $n$ 的位置，直接套一層二分搜就可以在 $O(n log C)$ 的時間解決這個問題了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
// 二分搜版本.cpp
// by LukeTseng

#include <bits/stdc++.h>

using namespace std;

bool canPlacePosters(const vector<int>& h, const vector<int>& w, int x) {
    int n = h.size();
    int k = w.size();
    int i = 0, poster = 0;

    while (poster < k) {
        int need = w[poster];
        int count = 0;

        while (i < n) {
            if (h[i] >= x) {
                count++;
                if (count == need) {
                    i++;
                    break;
                }
            } else {
                count = 0;
            }
            i++;
        }

        if (count < need) return false;
        poster++;
    }
    return true;
}

int main() {
    int n, k;
    cin >> n >> k;

    vector<int> h(n);
    for (int i = 0; i < n; ++i) cin >> h[i];

    vector<int> w(k);
    for (int i = 0; i < k; ++i) cin >> w[i];

    int low = 1, high = *max_element(h.begin(), h.end());
    int ans = 0;

    while (low <= high) {
        int mid = (low + high) / 2;
        if (canPlacePosters(h, w, mid)) {
            ans = mid;
            low = mid + 1;
        } else {
            high = mid - 1;
        }
    }

    cout << ans;
    return 0;
}

習題

  1. Zerojudge APCS 2017 年 3 月第 3 題 - 基地台：https://zerojudge.tw/ShowProblem?problemid=c575

題目說明：

  • $N$ 個服務點座標 $P[0 \cdots N-1]$ 。
  • 要架設 $K$ 個基地台，每個基地台可服務的範圍為一個區間，長度為 $D = 2R$ 。
  • 目標是找出最小的整數 $D$ ，使得用 $K$ 個長度為 $D$ 的區間，能覆蓋所有服務點。
1
2
0    1  2  3  4  5  6  7  8  9
     ▲  ▲        ▲     ▲  ▲

假設 $K = 1$ ，則最小直徑為 $7$ ，只有一個的話就放在 $1$ 跟 $8$ 兩個服務點中間，也就是 $4.5$ （取中位數）。

而 $4.5$ 到 $1$ 的距離為 $|4.5 - 1| = 3.5$ ，這個就是半徑了，而另一邊也依此類推 $|4.5 - 8| = 3.5$ ，因此 $D = 3.5 \times 2 = 7$ 。

解題思路：

  1. 排序服務點 $P[i]$ 。
  2. 二分搜最小直徑 $D$ ：由於題目保證最小直徑為整數，且 $D$ 至少為 $1$ ，最大可能為最大座標差（最大點 - 最小點），因此可在 $[1, max(P)-min(P)]$ 區間中對 $D$ 做二分搜。
  3. 判斷是否能在這個 $D$ 下，用 $K$ 個基地台覆蓋所有點。
    • 此為貪婪策略問題：
      • 由左往右掃，遇到一個點沒被覆蓋，就以這個點作為左界，蓋一個基地台（長度為 $D$ ）。
      • 然後跳過所有在這個基地台範圍內的點（即從 $P[i]$ 開始，直到 $P[j] > P[i] + D$ 才停止）
      • 重複此過程，每次都算一個新的基地台。
      • 最後看總共用了幾個基地台 used，若 used <= K，則代表這個 $D$ 可行。
  4. 若某個 $D$ 可行，則繼續去試更小的 $D$ （右界縮小），否則代表 $D$ 太小，左界往右擴。

註： $D$ 最大可能為最大座標差這件事，是從 $K = 1$ 去看的，因為你只有一個基地台可以架，又要涵蓋所有服務點，那 $D$ 不就最大座標 - 最小座標。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
#include <bits/stdc++.h>

using namespace std;

// 判斷在直徑為 D 的情況下，是否能用 K 個基地台覆蓋所有服務點
bool check(const vector<int>& P, int K, int D) {
    int N = P.size();
    int count = 0; // 紀錄已使用的基地台數量
    int i = 0; // 掃描目前位置

    // 貪心法，從左至右覆蓋服務點
    while (i < N) {
        int cover_start = P[i]; // 當前基地台左邊緣為第 i 個服務點
        int cover_end = cover_start + D; // 此基地台可覆蓋範圍為 [cover_start, cover_end]
        count++; // 使用了一個基地台

        // 繼續跳過所有在此基地台覆蓋範圍內的服務點
        while (i < N && P[i] <= cover_end) {
            i++;
        }
    }

    // 如果所需基地台數量小於等於 K，代表此直徑可行
    return count <= K;
}

int main() {
    int N, K;
    cin >> N >> K;
    
    vector<int> P(N);
    for (int i = 0; i < N; ++i) {
        cin >> P[i];
    }

    sort(P.begin(), P.end());

    // 找出最小與最大座標，用來設定二分搜左右界 l, r
    int min_pos = *min_element(P.begin(), P.end());
    int max_pos = *max_element(P.begin(), P.end());
    
    int l = 1;
    int r = max_pos - min_pos;
    
    int ans = r; // 答案預設為最大直徑，之後再縮小

    // 二分搜尋，找最小可行直徑
    
    while (l <= r) {
        int mid = (l + r) / 2;

        if (check(P, K, mid)) {
            ans = mid;
            r = mid - 1;
        } else { 
            l = mid + 1;
        }
    }

    cout << ans;
    
    return 0;
}

後面還有三題，但依我現在程度來說真的太難了XD，完全做不出來。