Skip to content

12 、二分

1、思想📌

在一个有序序列上，每次把搜索范围缩小一倍

2、前提📌

序列单调有序，无序无法二分，需要先排序

3、常见思路📌

1
2
3
4
5
6
7
while (L < R) {            // 一直二分，直到[L, R]缩小到L = R
    int mid = (L + R) / 2; // mid是[L, R]的中间值
    if (check(mid))
        R = mid; // 答案在左半部分，R = mid
    else         // 答案在右半部分，L = mid + 1
        L = mid + 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
29
30
31
32
33
34
35
36
int find(int q) {
    int l = 0, r = n + 1; // 开区间
    while (l + 1 < r) {   // l+1=r时结束
        int mid = (l + r) / 2;
        if (a[mid] <= q)
            l = mid;
        else
            r = mid;
    }
    return 1;
}
//--------------------------------------------------
int find(int q) {
    int l = 1, r = n; // 闭区间
    while (l < r) {   // l+1=r时结束
        int mid = (l + r) / 2;
        if (a[mid] <= q)
            l = mid;
        else
            r = mid;
    }
    return 1;
}
//--------------------------------------------------
int find(int q) {
    int ans = 0;
    int l = 1, r = n; // 闭区间
    while (l <= r) {  // l=r+1时结束
        int mid = (l + r) >> 1;
        if (a[mid] <= q)
            ans = mid,
            l = mid + 1;
        else r = mid - 1;
    }
    return ans;
}

4、经典应用📌

①最小值最大化📌

Question

e.g.“牛棚”问题

一条直线上\(n\)个点，选取\(k\)个点，其中某两点距离是所有距离中最小的，目的是让这个最小值\(D\)最大

猜测\(D\)是总长度\(L\)，接下来二分操作

②最大值最小化📌

Question

e.g.“序列划分”问题:

有一个包含\(n\)个正整数的序列，把它划分成\(k\)个子序列，每个子序列是原数列的一个连续部分，第\(i\)个子序列的和为\(S_i\)。在所有\(S\)中，有一个最大值。问如何划分，才能使最大的\(S\)最小?

这就是“最大值(所有子序列和的最大值)最小化”。

例如序列\({2,2,3,4,5,1}\),将其划分成\(k=3\)个连续的子序列。

下面举例2种分法:\({(2,2,3)、(4,5)、(1)}\)，子序列和分别是\(7、9、1\),最大值是\(9\)；\({(2,2,3)、(4)、(5,1)}\),子序列和是\(7、4、6\),最大值是\(7\)。第2种分法比第1种好。

用二分，在[max,sum]范围内找满足条件的x，max是序列中最大元素的值，sum是所有元素的和

例题📌

e.g.26 [蓝桥杯 2017 省 AB] 分巧克力📌

题目描述

儿童节那天有 \(K\) 位小朋友到小明家做客。小明拿出了珍藏的巧克力招待小朋友们。

小明一共有 \(N\) 块巧克力，其中第 \(i\) 块是 \(H_i \times W_i\) 的方格组成的长方形。

为了公平起见，小明需要从这 \(N\) 块巧克力中切出 \(K\) 块巧克力分给小朋友们。切出的巧克力需要满足：

  1. 形状是正方形，边长是整数。

  2. 大小相同。

例如一块 \(6 \times 5\) 的巧克力可以切出 \(6\) 块 \(2 \times 2\) 的巧克力或者 \(2\) 块 \(3 \times 3\) 的巧克力。

当然小朋友们都希望得到的巧克力尽可能大，你能帮小 \(H_i\) 计算出最大的边长是多少么？

输入格式

第一行包含两个整数 \(N\) 和 \(K\)。\((1 \le N,K \le 10^5)\)。

以下 \(N\) 行每行包含两个整数 \(H_i\) 和 \(W_i\)。\((1 \le H_i,W_i \le 10^5)\)。

输入保证每位小朋友至少能获得一块 \(1 \times 1\) 的巧克力。

输出格式

输出切出的正方形巧克力最大可能的边长。

样例

样例输入 

1
2
3
2 10  
6 5  
5 6

样例输出 

1
2

提示

蓝桥杯 2022 省赛 A 组 I 题。

 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
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1e5 + 10;
struct node {
    int width, height;
} e[N];
int n, k;
bool check(int mid) {
    int cnt = 0; // 统计切出的正方形块数
    for (int i = 1; i <= n; i++) {
        // 当前矩形可以切出的正方形数量为(width / mid) * (height / mid)
        cnt += (e[i].width / mid) * (e[i].height / mid);
        // 如果切出的块数已经达到或超过k，返回true
        if (cnt >= k) {
            return true;
        }
    }
    return false; // 如果所有矩形都遍历完还不足k块，返回false
}

int32_t main() {
    cin >> n >> k;
    for (int i = 1; i <= n; i++) {
        cin >> e[i].width >> e[i].height;
    }
    int l = 1, r = 1e9;
    int mid, ans = 0;
    // 二分搜索
    while (l <= r) {
        mid = (l + r) >> 1; // 计算中间值
        if (check(mid)) {
            ans = mid; // 如果当前边长可行，记录答案
            l = mid + 1; // 尝试更大的边长
        } else {
            r = mid - 1; // 如果当前边长不可行，尝试更小的边长
        }
    }

    cout << ans << endl; // 输出最大的边长
}

⭐e.g.27 奶牛晒衣服📌

题目背景

熊大妈决定给每个牛宝宝都穿上可爱的婴儿装 。但是由于衣服很湿，为牛宝宝晒衣服就成了很不爽的事情。于是，熊大妈请你（奶牛）帮助她完成这个重任。

题目描述

一件衣服在自然条件下用一秒的时间可以晒干 \(a\) 点湿度。抠门的熊大妈只买了一台烘衣机 。使用用一秒烘衣机可以让一件衣服额外烘干 \(b\) 点湿度（一秒晒干 \(a+b\) 湿度），但在同一时间内只能烘一件衣服。现在有 \(n\) 件衣服，第 \(i\) 衣服的湿度为 \(w_i\)（保证互不相同），要你求出弄干所有衣服的最少时间（湿度为 \(0\) 为干 ）。

输入格式

第一行三个整数，分别为 \(n,a,b\)。 接下来 \(2\) 到 \(n+1\) 行，第 \(i\) 行输入 \(w_i\)。

输出格式

一行，弄干所有衣服的最少时间。

样例

样例输入 

1
2
3
4
3 2 1
1
2
3

样例输出 

1
1

提示

样例解释

让机器烘第三件衣服即可一秒完成。

数据范围

\(1 \le w_i,a,b,n \le 5 \times 10^5\)

e.g.28 求阶乘📌

问题描述

满足 \(N!\) 的末尾恰好有 \(K\)个 0 的最小的 \(N\) 是多少?

如果这样的 \(N\)不存在输出 \(−1\) 。

输入格式

一个整数 \(K\)。

输出格式

一个整数代表答案。

样例输入

1
2

样例输出

1
10

评测用例规模与约定

对于 100% 的数据, \(1≤K≤10^{18}\).

Tip

二分优化：\(n\)递增，尾零数也单调递增，符合二分条件

末尾零的个数由因子 \(5\) 的个数决定。因为每个 \(5\) 必须搭配一个 \(2\) 才能生成一个零，而因子 \(2\) 的个数远多于因子 \(5\)，因此问题转化为计算 \(N\) 的因子 \(5\) 的个数。

 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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll k;
//计算N！末尾有几个0
ll check(ll mid) {      
    ll cnt = 0;
    while (mid) {
        cnt += (mid / 5);
        mid /= 5;
    }
    return cnt;
}
int main() {
    cin >> k;
    ll l = 1, r = 9e18, mid, ans = 0;
    while (l <= r) {
        mid = l + r >> 1;
        //mid尾数0超过k，说明mid大了
        if (check(mid) >= k) {
            ans = mid;
            r = mid - 1;
        } else//mid 小了
            l = mid + 1;
    }
    if (check(ans) == k)
        cout << ans << endl;
    else
        cout << -1 << endl;
    return 0;
}

e.g.29 [蓝桥杯 2022 国 B] 卡牌📌

题目描述

这天，小明在整理他的卡牌。

他一共有 \(n\) 种卡牌，第 \(i\) 种卡牌上印有正整数数 \(i(i \in[1, n])\), 且第 \(i\) 种卡牌现有 \(a_{i}\) 张。

而如果有 \(n\) 张卡牌，其中每种卡牌各一张，那么这 \(n\) 张卡牌可以被称为一套牌。小明为了凑出尽可能多套牌，拿出了 \(m\) 张空白牌, 他可以在上面写上数 \(i\)，将其当做第 \(i\) 种牌来凑出套牌。然而小明觉得手写的牌不太美观，决定第 \(i\) 种牌最多手写 \(b_{i}\) 张。

请问小明最多能凑出多少套牌?

输入格式

输入共 3 行，第一行为两个正整数 \(n\)，\(m\) 。

第二行为 \(n\) 个正整数 \(a_{1}, a_{2}, \ldots, a_{n}\) 。

第三行为 \(n\) 个正整数 \(b_{1}, b_{2}, \ldots, b_{n}\) 。

输出格式

一行，一个整数表示答案。

样例

样例输入 

1
2
3
4 5
1 2 3 4
5 5 5 5

样例输出 

1
3

提示

【样例说明】

这 \(5\) 张空白牌中，拿 \(2\) 张写 \(1\)，拿 \(1\) 张写 \(2\)，这样每种牌的牌数就变为了 \(3,3,3,4\)，可以凑出 \(3\) 套牌，剩下 \(2\) 张空白牌不能再帮助小明凑出一套。

【评测用例规模与约定】

对于 \(30 \%\) 的数据，保证 \(n \leq 2000\);

对于 \(100 \%\) 的数据，保证 \(n \leq 2 \times 10^{5} ; a_{i}, b_{i} \leq n ; m \leq n^{2}\) 。

蓝桥杯 2022 国赛 B 组 C 题。

 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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 2e5 + 10;
ll n, m;
ll a[N], b[N];
bool check(ll mid) {
    ll cnt = m;
    for (int i = 1; i <= n; i++) {
        if (a[i] >= mid)
            continue;
        else {
            ll k = mid - a[i];
            if (k > b[i])
                return false;
            cnt -= k;
            if (cnt < 0)
                return false;
        }
    }
    return true;
}
int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    for (int i = 1; i <= n; i++)
        cin >> b[i];
    ll l = 0, r = 4e5, mid, ans = 0;
    while (l <= r) {
        mid = l + r >> 1;
        if (check(mid)) {
            ans = mid;
            l = mid + 1;
        } else
            r = mid - 1;
    }
    cout << ans << endl;
    return 0;
}

e.g.30 [蓝桥杯 2022 省 A] 青蛙过河📌

题目描述

小青蛙住在一条河边，它想到河对岸的学校去学习。小青蛙打算经过河里的石头跳到对岸。

河里的石头排成了一条直线，小青蛙每次跳跃必须落在一块石头或者岸上。不过，每块石头有一个高度，每次小青蛙从一块石头起跳，这块石头的高度就会下降 \(1\)，当石头的高度下降到 \(0\) 时小青蛙不能再跳到这块石头上（某次跳跃后使石头高度下降到 \(0\) 是允许的)。

小青蛙一共需要去学校上 \(x\) 天课，所以它需要往返 \(2x\) 次。当小青蛙具有一个跳跃能力 \(y\) 时，它能跳不超过 \(y\) 的距离。

请问小青蛙的跳跃能力至少是多少才能用这些石头上完 \(x\) 次课。

输入格式

输入的第一行包含两个整数 \(n, x\), 分别表示河的宽度和小青蛙需要去学校的天数。请注意 \(2x\) 才是实际过河的次数。

第二行包含 \(n-1\) 个非负整数 \(H_{1}, H_{2}, \cdots, H_{n-1}\), 其中 \(H_{i}>0\) 表示在河中与 小青蛙的家相距 \(i\) 的地方有一块高度为 \(H_{i}\) 的石头，\(H_{i}=0\) 表示这个位置没有石头。

输出格式

输出一行, 包含一个整数, 表示小青蛙需要的最低跳跃能力。

样例

样例输入 

1
2
5 1
1 0 1 0

样例输出 

1
4

提示

【样例解释】

由于只有两块高度为 \(1\) 的石头，所以往返只能各用一块。第 \(1\) 块石头和对岸的距离为 \(4\)，如果小青蛙的跳跃能力为 \(3\) 则无法满足要求。所以小青蛙最少需要 \(4\) 的跳跃能力。

【评测用例规模与约定】

对于 \(30 \%\) 的评测用例，\(n \leq 100\);

对于 \(60 \%\) 的评测用例，\(n \leq 1000\);

对于所有评测用例，\(1 \leq n \leq 10^{5}, 1 \leq x \leq 10^{9}, 0 \leq H_{i} \leq 10^{4}\) 。

蓝桥杯 2022 省赛 A 组 F 题。

 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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 2e5 + 10;
ll n, x, a[N], s[N];
bool check(ll mid) {
    for (int i = 1; i <= n - mid; i++) {
        if (s[i + mid - 1] - s[i - 1] < 2 * x)
            return false;
    }
    return true;
}
int main() {
    cin >> n >> x;
    for (int i = 1; i <= n - 1; i++)
        cin >> a[i];
    for (int i = 1; i <= n - 1; i++)
        s[i] = s[i - 1] + a[i];
    ll l = 1, r = 1e5, mid, ans = 0;
    while (l <= r) {
        mid = l + r >> 1;
        if (check(mid)) {
            ans = mid;
            r = mid - 1;
        } else
            l = mid + 1;
    }
    cout << ans << endl;
    return 0;
}

e.g.31 管道📌

问题描述

有一根长度为 \(len\)的横向的管道，该管道按照单位长度分为 \(len\) 段，每一段的中央有一个可开关的阀门和一个检测水流的传感器。

一开始管道是空的，位于 \(L_i\) 的阀门会在 \(S_i\) 时刻打开，并不断让水流入管道。

对于位于 \(L_i\)的阀门，它流入的水在 \(T_i\) (\(T_i≥S_i\)) 时刻会使得从第 \(L_i−(T_i−S_i)\)段到第 \(L_i+(T_i−S_i)\)段的传感器检测到水流。

求管道中每一段中间的传感器都检测到有水流的最早时间。

输入格式

输入的第一行包含两个整数 \(n,len\)，用一个空格分隔，分别表示会打开的阀门数和管道长度。

接下来 \(n\)行每行包含两个整数 \(L_i,S_i\)，用一个空格分隔，表示位于第 \(L_i\)段管道中央的阀门会在 \(S_i\)时刻打开。

输出格式

输出一行包含一个整数表示答案。

样例输入

1
2
3
4
3 10
1 1
6 5
10 2

样例输出

1
5

 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
53
54
/*
pair<int,int> p 数据类型
相当于只有两个元素的struct，更简易
*/
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pii;
const int N = 2e5 + 10;
ll n, len, a[N];
pii p[N];
bool cmp(pii p1, pii p2) {
    return p1.first < p2.first;
}
bool check(ll mid) {
    vector<pii> v;
    for (int i = 1; i <= n; i++) {
        if (p[i].second <= mid) {
            ll l = max(1ll, p[i].first - (mid - p[i].second));
            ll r = min(len, p[i].first + (mid - p[i].second));
            v.push_back({l, r});
        }
    }
    sort(v.begin(), v.end(), cmp);
    ll l = v[0].first, r = v[0].second;
    if (l != 1)
        return false;
    for (int i = 1; i < v.size(); i++) {
        ll x = v[i].first, y = v[i].second;
        if (x > r + 1)
            return false;
        else
            r = max(r, y);
    }
    if (r != len)
        return false;
    return true;
}
int main() {
    cin >> n >> len;
    for (int i = 1; i <= n; i++)
        cin >> p[i].first >> p[i].second;
    ll l = 1, r = 2e9, mid, ans = 0;
    while (l <= r) {
        mid = l + r >> 1;
        if (check(mid)) {
            ans = mid;
            r = mid - 1;
        } else
            l = mid + 1;
    }
    cout << ans << endl;
    return 0;
}