二分搜

對於一個函數 $F(n)$ ，如果存在一個 x，對於所有 $\geq x$ 的 a， $F(a)=$ true，反之 $F(a)=$ false，基於這樣的單調性，就可以用二分搜。

T binary_search()
{
    while (L < R)
    {
        int M = (L + R) >> 1;
        if (F(M))
            R = M;
        else
            L = M + 1;
    }
    return L;
}

有些題目為 "最多/最少為何會成立"，那麼如果你可以在良好的時間檢查出 " 如果代價是 $x$ ，那可不可以達成目標 "，並且 $x$ 具有單調性，那麼你可以轉換成 " 如果代價是 $x$ ，那可不可以達成目標 " 傳換成 $F(x)$ ，對答案（x）進行二分搜。二分搜要注意兩件事，一個是無限迴圈，要避免它可以在腦中先模擬一下。一個是在實數中二分搜，因為實數的稠密性，題目會有誤差容忍值（例如 $10^{-6}$ )，只要在誤差內都是容許的。

最小瓶頸樹

給定一張圖，求一顆生成樹，樹的最大邊權值最小。

枚舉最大邊權值 $w$ ，用 DFS/BFS 檢查 $\leq w$ 的邊是否可以將所有點相連，如果可以，最大邊權值會 $\leq w$ ，否則會 $>w$ 。

三分搜

對於凸函數（例如 $y=F(x)=x^2$ )，我們想要找尋其極值，意謂其左右兩側皆各自遞增/遞減，我們可以利用三分搜來解決（二分搜只能解決全體單調性，不能解決有兩邊的）。考慮三分後從左到右四個採樣點的關係

$S(a) < S(b) < S(c) < S(d)$ ，此時最小值一定不在最右邊
$S(a) > S(b) < S(c) < S(d)$ ，此時最小值一定不在最右邊
$S(a) > S(b) > S(c) < S(d)$ ，此時最小值一定不在最左邊
$S(a) > S(b) > S(c) > S(d)$ ，此時最小值一定不在最左邊

這段描敘還可以再簡化：

$S(b) < S(c)$ ，此時最小值一定不在最右邊
$S(b) > S(c)$ ，此時最小值一定不在最左邊

每次迭代先求出 $b,c$ 的值，再利用簡化過的規則，使區間減少 $\frac{1}{3}$ 。令 $EPS$ 為誤差容忍值，一開始的範圍為 $[L,R]$ ，迴圈大約需迭代 $\log_{1.5}\frac{R-L}{EPS}$ 次（ $\log_{1.5}10$ 大約為 $5.6$ )。

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;
}

另外一種做法，會固定迴圈迭代次數。

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

給定 $N$ 個開口向上的二次曲線 $S_i$ ，令 $F(x)=max{S_i(x)}$ ，求 $F(x)$ 的最小值。

多個二次函數取最大值的結果還是一個二次函數，利用三分搜搜尋極值。

參考程式碼

#pragma GCC optimize("O2")
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
using ULL = unsigned long long;
using PII = pair<int, int>;
using PLL = pair<LL, LL>;
using VI = vector<int>;
using VVI = vector<vector<int>>;
const int INF = 1e9;
const int MXN = 1e4 + 5;
const int MXV = 0;
const double EPS = 1e-9;
const int MOD = 1e9 + 7;
#define MP make_pair
#define PB push_back
#define F first
#define S second
#define FOR(i, L, R) for (int i = L; i < (int)R; ++i)
#define FORD(i, L, R) for (int i = L; i > (int)R; --i)
#define IOS                                                                    \
    cin.tie(nullptr);                                                          \
    cout.tie(nullptr);                                                         \
    ios_base::sync_with_stdio(false);
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

今天有 $N$ 個人要參加鐵人二項，有跑步和騎腳踏車，總長 $L$ 公里，第 $N$ 位參賽者賄賂主辦方，想要得到第一名，主辦方知道每個人跑步和騎腳踏車的速度 $vr_i,vk_i$ ，並且可以隨意決定跑步和騎腳踏車的距離，求第 $N$ 位參賽者是否能獲得第一，如果可以，輸出領先第二名的秒數和主辦方設定跑步和騎腳踏車的距離。

設跑步 $r$ 公里，那麼騎腳踏車 $L-r$ 公里，第 $i$ 位參賽者要花費 $t_i(r)=\frac{r}{vr_i}+\frac{k}{vk_i}$ ，前 $N-1$ 位參賽者花費時間取最小值，再減去第 $N$ 位參賽者的時間，會是一個凸函數(可以參考這篇文章)，同樣也能用三分搜找出極值

參考程式碼

#pragma GCC optimize("O2")
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
using ULL = unsigned long long;
using PII = pair<int, int>;
using PLL = pair<LL, LL>;
using VI = vector<int>;
using VVI = vector<vector<int>>;
const int INF = 1e9;
const int MXN = 1e4 + 5;
const int MXV = 0;
const double EPS = 1e-9;
const int MOD = 1e9 + 7;
#define MP make_pair
#define PB push_back
#define F first
#define S second
#define FOR(i, L, R) for (int i = L; i < (int)R; ++i)
#define FORD(i, L, R) for (int i = L; i > (int)R; --i)
#define IOS                                                                    \
    cin.tie(nullptr);                                                          \
    cout.tie(nullptr);                                                         \
    ios_base::sync_with_stdio(false);
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(i, 1, n - 1) 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(i, 0, n) 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);
    }
}

例題練習

最小瓶頸樹
- UVa 01395 - Slim Span