二分答案

这两道题可以带学带练，思路几乎是一样的。学完二分你会发现，精髓其实在于思考如何借助二分写函数体 check：我们有了查找的思路，难点在于把求最优解的问题，转化为给定一个值 Mid，判定是否存在一个可行方案达到 Mid。

P1873 砍树

P1873 [COCI 2011/2012 #5] EKO / 砍树 - 洛谷

我们要找一个合适的高度去切，刚好用二分来确定最后的 H。

易错点：

  • 右边界 r 可以直接赋成 400000，也可以赋成数组里的最大值。
  • check 里算到 ans >= m 就提前返回，不用等全部算完，超过即符合题意。
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
#include<bits/stdc++.h>
using namespace std;
using ll = long long;

ll n, m;
vector<ll> a;

bool check(int h) {
    ll ans = 0;
    for (int i = 1; i <= n; i++) {
        if (h < a[i]) ans += a[i] - h;
        if (ans >= m) return true;   // 只要超过就符合题意
    }
    return false;
}

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

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

    int l = 0, r = 400000, mid;   // 这里 r 也可以赋值为 a 中的最大值
    while (l <= r) {
        mid = (l + r) / 2;
        if (check(mid)) l = mid + 1;   // 符合的话，高度还可以再上升
        else r = mid - 1;
    }

    cout << mid << endl;
    return 0;
}

举一反一：P2440 木材加工

P2440 木材加工 - 洛谷

我们还是光头强 抓住上题的思路和模板，不看题解也可以自己做出来 AC。区别只在 check 的统计方式：

1
2
3
4
5
6
7
8
bool check(ll l) {
    ll cnt = 0;
    for (ll num : L) {
        if (num >= l) cnt += num / l;
        if (cnt >= k) return true;
    }
    return false;
}

其他部分没差别。

P1182 数列分段 Section II

P1182 数列分段 Section II - 洛谷

这道题关键是 check 部分的实现，怎么和二分联系起来。换句话说，能不能做到切分成 <= m 段，且每段的 Max 都小于某个值 K——这个 K 就是我们能二分的量。

K 的最大值取整个数组的和，最小值取其中最大的那一项。

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
#include<bits/stdc++.h>
using namespace std;
using ll = long long;

ll n, m;
vector<ll> a;

bool check(ll k) {
    int cnt = 1;
    ll sum = 0;
    for (int i = 1; i <= n; i++) {
        if (sum + a[i] <= k) sum += a[i];
        else {
            sum = a[i];
            cnt++;
        }
        if (cnt > m) return false;
    }
    return true;
}

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

    cin >> n >> m;
    a.resize(n + 1);
    ll left = 0, right = 0;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        left = max(left, a[i]);
        right += a[i];
    }

    while (left < right) {
        ll mid = (right + left) / 2;
        if (check(mid)) right = mid;
        else left = mid + 1;
    }

    cout << left << endl;
    return 0;
}

P1678 烦恼的高考志愿

P1678 烦恼的高考志愿 - 洛谷

这道题思路差不多，但是可以借助 upper_bound 和 lower_bound 直接算，省去手写二分的麻烦。

总结

  • 核心思想：把「求最优解」转化为「给定一个 Mid，判定是否存在可行方案」。
  • check 怎么写：围绕「这个 Mid 能不能达成目标」去设计判定函数，往往是整个二分答案题最难的部分。
  • 边界：右边界可以赋成数组最大值 / 总和；check 内能提前剪枝就提前返回。
  • 有的题（如 P1678）可以直接用 lower_bound / upper_bound，比手写二分更省事。