27 · 二分查找与二分答案

两个看起来很不一样的问题，答案是同一个。

• 问题 A：给 n 个单调不减的数，m 次询问“x 第一次出现在哪个位置”。线性扫一遍是 O(nm)，n = 10⁶、m = 10⁵ 时 10¹¹ 次比较，TLE。
• 问题 B：求“锯片最高能设到多少米，砍下的木材仍不少于 M”。从 0 逐个高度试是 O(N × maxH)，10⁶ × 4×10⁵ = 4×10¹¹ 次，TLE。

A 的答案是二分查找：有序 ⇒ 每次比较就能排除一半。B 的答案是二分答案：把“求最优”换成“判定可行”，可行的取值是一段连续的区间，而“是否可行”沿大小方向单调 ⇒ 也能每次砍掉一半。两者都是 O(log) 次判断，log₂10⁶ ≈ 20，log₂4×10⁵ ≈ 19。

这道题手写二分只要 8 行，但标准库已经把“第一个不小于 x 的位置”这件事做成了函数。先把它彻底看清：两个函数只差一个符号，却对应完全不同的语义。

int a[7] = {0, 1, 2, 2, 2, 5, 7};        // a[1..6] 是数据，a[0] 空着
int p = lower_bound(a + 1, a + 7, 2) - a;   // 第一个 >= 2  ->  p = 2
int q = lower_bound(a + 1, a + 7, 3) - a;   // 第一个 >= 3  ->  q = 5（a[5] = 5）
int r = lower_bound(a + 1, a + 7, 9) - a;   // 全都 < 9     ->  r = 7（尾后）
// r == 7 已经超出 a[6]，所以 a[r] 是越界读！必须先判 r <= 6

int lo = lower_bound(a + 1, a + n + 1, x) - a;   // 第一个 >= x
int up = upper_bound(a + 1, a + n + 1, x) - a;   // 第一个 >  x

int cnt = up - lo;            // x 出现的次数
bool has = (lo < up);         // x 是否出现
int le  = up - 1;             // 最后一个 <= x 的位置

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 1000005;        // n ≤ 10⁶，1-based 用到 a[n]
int a[MAXN];

int main() {
    ios::sync_with_stdio(false); // 10⁶ 个读入，不关同步很容易 TLE
    cin.tie(nullptr);

    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= n; ++i) cin >> a[i];

    for (int i = 1; i <= m; ++i) {
        int q;
        cin >> q;
        // 区间 [a+1, a+n+1)：正好盖住 a[1]..a[n]，右端是尾后指针
        int p = lower_bound(a + 1, a + n + 1, q) - a;   // 第一个 >= q 的下标

        if (i > 1) cout << ' ';                       // 行末不留多余空格
        if (p <= n && a[p] == q) cout << p;           // 找到：p 就是第一次出现的位置
        else                     cout << -1;          // 全比 q 小，或没有等于 q 的数
    }
    cout << '\n';
    return 0;
}

标准库好用，但比赛里经常需要变形：找“最后一个满足条件的”“最小的可行值”“答案在 long long 范围”。这些都得自己写二分。手写二分只有两种正确姿势，先把它们刻下来。

int a[9] = {0, 1, 2, 2, 2, 5, 7, 7, 9};    // a[1..8]

// 写法 B：找第一个 >= 2 的下标
int lo = 1, hi = 8 + 1;                       // 半开区间 [1, 9]
while (lo < hi) {
    int mid = (lo + hi) >> 1;                 // 向下取整
    if (a[mid] >= 2) hi = mid;                // mid 可能是答案，留着（不 -1）
    else             lo = mid + 1;            // mid 不可能是答案，扔掉
}
cout << lo << "\n";                           // 2

// 写法 A：同样的目标，另一种记录方式
int l = 1, r = 8, ans = -1;
while (l <= r) {
    int mid = (l + r) >> 1;
    if (a[mid] >= 2) { ans = mid; r = mid - 1; }
    else               l = mid + 1;
}
cout << ans << "\n";                          // 2

二分查找是在数组上二分；二分答案是在答案的取值上二分。两者的代码骨架一模一样，区别只在于比较的对象：前者比 a[mid] 与 x，后者比 check(mid) 与 true。

• 答案可枚举：答案是一个整数，且有明确的下界 lo 和上界 hi（或实数区间）。
• 判定函数 check(v)：只回答“取 v 行不行”，不回答“v 是不是最优”。它必须与题目最优值无关，复杂度 O(n) 或更低。
• 单调性：v 从小往大，check 的结果必须形如“真真…真假假…假”（或反过来）。只有这样才能用“比较结果”排除一半候选。
• 收尾：解是“最后一个可行的”还是“第一个可行的”，决定 lo / hi / ans 谁被保留、最后返回谁。

bool ok(int H) {
    long long sum = 0;
    for (int i = 1; i <= n; ++i)
        if (a[i] > H) sum += a[i] - H;   // 只有比锯片高的树贡献木材
    return sum >= M;
}

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 1000005;
int a[MAXN];
int n;
long long M;

// check(H)：锯片升到 H 米，能不能拿到至少 M 米木材
bool ok(int H) {
    long long sum = 0;
    for (int i = 1; i <= n; ++i) {
        if (a[i] > H) sum += a[i] - H;   // 高过锯片的部分才被锯下
        if (sum >= M) return true;       // 已经够了，后面不用看
    }
    return sum >= M;
}

int main() {
    ios::sync_with_stdio(false);   // 10⁶ 个读入，而且要被扫 19 遍
    cin.tie(nullptr);

    cin >> n >> M;
    int mx = 0;
    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
        if (a[i] > mx) mx = a[i];
    }

    int lo = 0, hi = mx, ans = 0;      // 答案一定在 [0, mx] 内
    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;  // 与 (lo+hi)/2 等价，但不会溢出
        if (ok(mid)) { ans = mid; lo = mid + 1; }   // 可行：记下来，再试着升高
        else         { hi = mid - 1; }              // 不可行：只能降
    }
    cout << ans << "\n";
    return 0;
}

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 100005;
int n, m;
long long a[MAXN];

// check(limit)：每段和都不超过 limit 时，最少要分成几段？不超过 m 段就可行
bool ok(long long limit) {
    int cnt = 1;              // 至少一段
    long long cur = 0;        // 当前这一段已经装了多少
    for (int i = 1; i <= n; ++i) {
        if (cur + a[i] <= limit) {
            cur += a[i];      // 塞得下就塞：段数越少越容易满足 "<= m"
        } else {
            ++cnt;            // 塞不下，a[i] 自己开一段
            cur = a[i];       // 注意不是 0，a[i] 已经在这一段里了
            if (cnt > m) return false;   // 段数只会增不会减，提前剪枝
        }
    }
    return cnt <= m;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> m;
    long long lo = 0, hi = 0;
    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
        hi += a[i];              // 上界：全部放进一段，一定可行
        lo = max(lo, a[i]);      // 下界：至少要装得下最大的那个数
    }

    while (lo < hi) {            // 半开写法：答案域 [lo, hi]
        long long mid = lo + (hi - lo) / 2;
        if (ok(mid)) hi = mid;        // 可行：mid 可能就是答案，保留
        else         lo = mid + 1;    // 不可行：mid 及更小全部排除
    }
    cout << lo << "\n";          // 循环结束时 lo == hi == 最小的可行上限
    return 0;
}