二分答案

二分答案是什么

在学习二分查找的时候，引入的例子，使用的是猜数字游戏，猜一个数字，反馈猜大了，还是猜小了。

二分答案，也是猜答案，看这个答案是猜大了，还是猜小了。不同的是，验证的过程变复杂了，需要写一个check()函数，进行验证

解题的时候往往会考虑枚举答案然后检验枚举的值是否正确。

把这里的枚举换成二分，直接减半运算，就变成了「二分答案」。

猜这个答案是否成立，是一个很有用的优化途径。

能否二分，有一个界定标准：状态的决策过程或者序列是否满足单调性或者可以局部舍弃

1247：河中跳房子

题意：从 0 跳到 L，中间有一些石头。最多可移走 m 个石头的情况下，最长的最短跳跃距离是多少

#include <bits/stdc++.h>

using namespace std;

const int N = 5e4 + 10;

int q[N];
int L, n, m;

bool check(int dist) {
    int last = 0, cnt = 0;
    for (int i = 1; i <= n + 1; i++) { 
        if (q[i] - last < dist) cnt++;  //小于最短跳跃距离，此点移除
        else last = q[i];
    }

    // 移除石头的个数，小于等于m
    // 跳跃距离，可以再长一点
    // 长了，就可以移除更多的石头
    // 返回true，可以跳的更长一点
    return cnt <= m; 
}

int main() {
    cin >> L >> n >> m;

    for (int i = 1; i <= n; i++) cin >> q[i];
    q[0] = 0, q[n + 1] = L;

    int l = 0, r = 1e9+10, ans = -1;
    while (l <= r) {
        int mid = (l + r) >> 1;
        if (check(mid)) l = mid + 1, ans = mid;
        else r = mid - 1;
    }

    cout << ans << '\n';

    return 0;
}

1242：网线主管

题意：有 n 个长短不一的网线，现在要剪出来 k 条长短一样的网线，希望这 k 条网线越长越好。问最长的长度

#include <bits/stdc++.h>

using namespace std;

const int N = 1e4 + 10;
const double eps = 1e-6;

double a[N];
int n, k;

bool check(double x) {
    int cnt = 0;
    for (int i = 0; i < n; i++)
        cnt += (int)(a[i] / x);

    if (cnt >= k) return true;
    else return false;
}

int main() {
    cin >> n >> k;
    for (int i = 0; i < n; i++) cin >> a[i];

    double l = 0.0, r = 2e9;
    int n = 100;
    while (n--) {
        double mid = (l + r) / 2;
        if (check(mid)) l = mid;
        else r = mid;
    }

    int res = (int)(r * 100);
    if (res == 0) printf("0.00\n");
    else printf("%.2lf\n", 1.0 * res / 100);  // 这道题目输出格式有亿点坑

    return 0;
}

P1083 [NOIP2012 提高组] 借教室

在这个题里，因为如果前一份订单都不满足，那么之后的所有订单都不用继续考虑；

而如果后一份订单都满足，那么之前的所有订单一定都可以满足，符合局部舍弃性，所以可以二分订单数量。

总结

只有20%的程序员，可以写好二分？

这个看起来不难，写起来却一坨屎。

我想你很快会有这种体验。

参考

维基百科-二分查找算法

二分 - OI Wiki

https://www.luogu.com.cn/article/sncheqxz

更新记录

2025/4/15，更新模板，更新例题