二分搜
對於一個函數 ，如果存在一個 ，對於所有 的 ， true (false)，反之 false(true)，基於這樣的單調性，就可以用二分搜找尋 。每次跌代會根據目前邊界中間值的結果，決定下次搜尋範圍為左半部分或右半部分。
搜尋範圍更新
下文會介紹兩種範圍更新的技巧。
輸出有 True 和 False 兩種結果， 有兩種分布情況：
- 情況 1：True 都在 False 的左邊，要找最右邊的 True
- True, True, True, True, False, False
- 情況 2：True 都在 False 的右邊，要找最左邊的 True
- False, False, True, True, True, True
紀錄搜尋範圍左右界： 和 為目前紀錄搜尋範圍左右界，情況 1 要注意無限迴圈的問題，解決辦法如程式碼所示。
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 | // 情況 1
T binary_search()
{
int L = 1, R = n;
while(L < R - 1) // 避免無限迴圈
{
int M = (L + R) >> 1;
if(f(M))L = M;
else R = M - 1;
}
if(L == r - 1 && f(R)) ++L;
if(!f(L))return -1;
return L;
}
// 情況 2
T binary_search()
{
int L = 1, R = n;
while(L < R)
{
int M = (L + R) >> 1;
if(f(M))R = M;
else L = M + 1;
}
if(L == n && !f(L))return -1;
return L;
}
|
紀錄 True 和 False 最後一次出現的位置：令 和 為 True 和 False 最後一次出現的位置，這種辦法的優勢在於兩種情況只差在初始化，較不容易打錯。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23 | // 情況 1
T binary_search()
{
int ok = 1, ng = n;
while(abs(ok - ng) > 1)
{
int M = (ok + ng) >> 1;
if(f(M))ok = M;
else ng = M;
}
}
// 情況 2
T binary_search()
{
int ok = n, ng = 1;
while(abs(ok - ng) > 1)
{
int M = (ok + ng) >> 1;
if(f(M))ok = M;
else ng = M;
}
}
|
注意事項
二分搜要注意兩件事，一個是無限迴圈，在「紀錄搜尋範圍左右界」部分有提到。一個是在實數中二分搜，因為實數的稠密性，題目會有誤差容忍值（例如 )，只要在誤差內都是容許的，在實作時會設一個數字 並使 或 。
有序序列二分搜
對排列好的序列，可直接使用 lower_bound 和 upper_bound。
| lower_bound(a, a + n, k); //最左邊 ≥ k 的位置
upper_bound(a, a + n, k); //最左邊 > k 的位置
upper_bound(a, a + n, k) - 1; //最右邊 ≤ k 的位置
lower_bound(a, a + n, k) - 1; //最右邊 < k 的位置
[lower_bound, upper_bound) //等於 k 的範圍
equal_range(a, a+n, k);
|
UVa 10474 - Where is the Marble?
給定一組數字，先將它們排序後，詢問數字 ，在第幾個位置。
二分搜基本練習。
參考程式碼
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 | #include <bits/stdc++.h>
using namespace std;
#define N 10010
int main()
{
int t = 0, n, q;
vector<int> a(N);
while (cin >> n >> q, n)
{
cout << "CASE# " << ++t << ":\n";
for (int i = 0; i < n; i++)
cin >> a[i];
sort(a.begin(), a.begin() + n);
for (int j = 1, x; j <= q; j++)
{
cin >> x;
auto it = lower_bound(a.begin(), a.begin() + n, x);
if (it == a.begin() + n || *it != x)
cout << x << " not found\n";
else
cout << x << " found at " << it - a.begin() + 1 << '\n';
}
}
}
|
UVa 11057 - Exact Sum
給定一組數字，找出兩個數字，數字和為 ，如果有多組解，輸出差距最小的一組。
先對序列排序，枚舉每個數字 ，利用二分搜判斷是否存在 。
參考程式碼
對答案二分搜
有些題目為 "最多/最少為何會成立"，那麼如果你可以在良好的時間檢查出 " 如果代價是 ，那可不可以達成目標 "，並且 具有單調性，那麼你可以轉換成 " 如果代價是 ，那可不可以達成目標 "，對答案（）進行二分搜。
UVa 12032 - The Monkey and the Oiled Bamboo
一開始位置在 ，依序抵達座標 ，找出最小的 滿足：每一次最多只能前進 步，如果這次前進 步，之後最多只能前進 步，以此類推。
二分搜答案 ， 代表一開始 是否可以題目要求，利用題目敘述實現 。
參考程式碼
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 | int n;
vector<int> v(MXN);
bool f(int k)
{
for (int i = 1; i <= n; ++i)
{
if (v[i] - v[i - 1] > k)
return false;
if (v[i] - v[i - 1] == k)
--k;
}
return true;
}
int main()
{
int t;
cin >> t;
v[0] = 0;
for (int ti = 1; ti <= t; ++ti)
{
cin >> n;
for (int i = 1; i <= n; ++i)
cin >> v[i];
int L = 1, R = v[n], ans = 0;
while (L <= R)
{
int M = (L + R) >> 1;
if (f(M))
{
ans = M;
R = M - 1;
}
else
L = M + 1;
}
cout << "Case " << ti << ": " << ans << '\n';
}
}
|
UVa 11413 - Fill the Containers
給定 個數字 ，要把它切割成 組數字，第 組數字和為 ，切割成本 ，請求出最小的 。
這題設 為成本是否可以 ， 的判斷方法為：從頭開始取數字，每一組盡可能累積到 ，取完 組後，看是否還有數字未取到。
參考程式碼
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 | vector<long long> v(MXN);
int n, m;
bool f(long long x)
{
int idx = 0;
for (int i = 0; i < m; ++i)
{
long long cur = 0;
while (idx < n && cur + v[idx] <= x)
{
cur += v[idx];
++idx;
}
}
return idx == n;
}
int main()
{
while (cin >> n >> m)
{
long long sum = 0;
for (int i = 0; i < n; ++i)
{
cin >> v[i];
sum += v[i];
}
long long L = 0, R = sum, ans = 0;
while (L <= R)
{
int M = (L + R) >> 1;
if (f(M))
{
R = M - 1;
ans = M;
}
else
L = M + 1;
}
cout << ans << '\n';
}
}
|
UVa 12190 - Electric Bill
給定電力價格表，你和你的鄰居合併計算電費為 元，分開計算的差額為 元，請問如果分開計算的情況下，你的電費為何(你的電費比較便宜)?
設 計算使用 度電的電費，先用二分搜找出兩個人總共使用的電量 ，接著二分搜你的電量 ，有以下三種情況：
參考程式碼
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 | long long bill(long long x)
{
if (x < 100)
return 2 * x;
if (x < 10000)
return 3 * (x - 100) + 200;
if (x < 1000000)
return 5 * (x - 10000) + 29900;
else
return 7 * (x - 1000000) + 4979900;
}
int main()
{
IOS;
int a, b;
while (cin >> a >> b, a || b)
{
long long tot = 0;
long long L = 0, R = 1000000000;
while (L <= R)
{
long long M = (L + R) >> 1;
long long res = bill(M);
if (res == a)
{
tot = M;
break;
}
if (res < a)
L = M + 1;
else
R = M - 1;
}
L = 0;
R = tot;
while (L <= R)
{
long long M = (L + R) >> 1;
long long res = bill(tot - M) - bill(M);
if (res == b)
{
cout << bill(M) << '\n';
break;
}
if (res < b)
R = M - 1;
else
L = M + 1;
}
}
}
|
最小瓶頸樹
最小瓶頸樹
給定一張圖，求一顆生成樹，樹的最大邊權值最小。
枚舉最大邊權值 ，用 DFS/BFS 檢查 的邊是否可以將所有點相連，如果可以，最大邊權值會 ，否則會 。
三分搜
對於凸函數（例如 )，我們想要找尋其極值，意謂其左右兩側皆各自遞增/遞減，我們可以利用三分搜來解決（二分搜只能解決全體單調性，不能解決有兩邊的）。
考慮三分後從左到右四個採樣點的關係：
-
-
，此時最小值一定不在最右邊
-
，此時最小值一定不在最右邊
-
，此時最小值一定不在最左邊
-
，此時最小值一定不在最左邊
這段描敘還可以再簡化：
-
，此時最小值一定不在最右邊
-
，此時最小值一定不在最左邊
每次迭代先求出 的值，再利用簡化過的規則，使區間減少 。令 為誤差容忍值，一開始的範圍為 ，迴圈大約需迭代 次（ 大約為 )。
1
2
3
4
5
6
7
8
9
10
11
12
13 | const double EPS = 1e−7;
double trinary_search(double L, double R)
{
while (R - L > EPS)
{
double mL = (L + L + R) / 3, mR = (L + R + R) / 3;
if (f(mR) > f(mL))
R = mR;
else
L = mL;
}
return L;
}
|
另外一種做法，會固定迴圈迭代次數。
1
2
3
4
5
6
7
8
9
10
11
12 | double trinary_search(double L, double R)
{
for (int i = 0; i < 300; ++i)
{
double mL = (L + L + R) / 3, mR = (L + R + R) / 3;
if (f(mR) > f(mL))
R = mR;
else
L = mL;
}
return L;
}
|
UVa 01476 - Error Curves
給定 個開口向上的二次曲線 ，令 ，求 的最小值。
多個二次函數取最大值的結果還是一個二次函數，利用三分搜搜尋極值。
參考程式碼
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 | int n;
double a[MXN], b[MXN], c[MXN];
double f(double x)
{
double ret = a[0] * x * x + b[0] * x + c[0];
FOR(i, 1, n) ret = max(ret, a[i] * x * x + b[i] * x + c[i]);
return ret;
}
double trinary_search(double L, double R)
{
for (int i = 0; i < 300; ++i)
{
double mL = (L + L + R) / 3, mR = (L + R + R) / 3;
if (f(mR) > f(mL))
R = mR;
else
L = mL;
}
return L;
}
int main()
{
int t;
cin >> t;
while (t--)
{
cin >> n;
FOR(i, 0, n) cin >> a[i] >> b[i] >> c[i];
cout << fixed << setprecision(4) << f(trinary_search(0.0, 1000.0)) << '\n';
}
}
|
UVa 10385 - Duathlon
今天有 個人要參加鐵人二項，有跑步和騎腳踏車，總長 公里，第 位參賽者賄賂主辦方，想要得到第一名，主辦方知道每個人跑步和騎腳踏車的速度 ，並且可以隨意決定跑步和騎腳踏車的距離，求第 位參賽者是否能獲得第一，如果可以，輸出領先第二名的秒數和主辦方設定跑步和騎腳踏車的距離。
設跑步 公里，那麼騎腳踏車 公里，第 位參賽者要花費 ，前 位參賽者花費時間取最小值，再減去第 位參賽者的時間，會是一個凸函數(可以參考這篇文章)，同樣也能用三分搜找出極值
參考程式碼
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 | int n;
double L;
double vr[MXN], vk[MXN];
double f(double r)
{
double t = r / vr[n - 1] + (L - r) / vk[n - 1];
double ret = r / vr[0] + (L - r) / vk[0];
for(int i = 1; i < n - 1; ++i) ret = min(ret, r / vr[i] + (L - r) / vk[i]);
return ret - t;
}
double trinary_search(double L, double R) // find max
{
for (int i = 0; i < 300; ++i)
{
double mL = (L + L + R) / 3, mR = (L + R + R) / 3;
if (f(mL) > f(mR))
R = mR;
else
L = mL;
}
return L;
}
int main()
{
while (cin >> L >> n)
{
for(int i = 0; i < n; ++i) cin >> vr[i] >> vk[i];
double ansL = trinary_search(0.0, L);
double ansT = f(ansL);
if (ansT < 0.00)
printf("The cheater cannot win.\n");
else
printf("The cheater can win by %.0lf seconds with r = %.2lfkm and "
"k = %.2lfkm.\n",
ansT * 3600.0, ansL, L - ansL);
}
}
|
例題練習