跳转至

J-L22 查找与二分

覆盖词条：KJ-31d/31e ｜ 先修：J-L20/L23

二分查找 · 判断存在

二分查找模板：判断存在（三种写法）1

二分查找：判断元素是否存在

题目描述

给出一个升序数组，\(q\) 次询问，每次询问一个数 \(x\) 是否在数组中。存在输出 YES，否则输出 NO。要求分别用三种二分写法实现。

输入格式

第一行两个整数 \(n, q\)；第二行 \(n\) 个升序整数；接下来 \(q\) 行每行一个询问 \(x\)。

输出格式

共 \(q\) 行，每行 YES 或 NO。

样例输入

1
2
3
4
5
6 3
1 3 5 7 9 11
7
4
11

样例输出

1
2
3
YES
NO
YES

数据范围

  • \(1 \le n, q \le 10^5\)
  • 数组元素与询问绝对值 \(\le 10^9\)

⬇ 点击下载数据包

写法一：l < r 收敛式

解题思路

收敛到最后只剩一个位置——它就是「第一个 \(\ge x\)」的位置，再判一次是否等于 \(x\)。这套写法的要点：l = mid + 1 与 r = mid 保证区间必缩小，退出时 \(l = r\)。

AC代码

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

int n, q;
vector<long long> a;

// 写法一：l < r 收敛式——退出时 l 指向「第一个 >= x」的位置，再判等
bool exist(long long x) {
    int l = 0, r = n - 1;
    while (l < r) {
        int mid = (l + r) / 2;
        if (a[mid] < x) l = mid + 1;
        else r = mid;
    }
    return a[l] == x;
}

int main() {
    cin >> n >> q;
    a.resize(n);
    for (auto& x : a) cin >> x;
    while (q--) {
        long long x;
        cin >> x;
        cout << (exist(x) ? "YES" : "NO") << "\n";
    }
    return 0;
}
写法二：l <= r + answer 记录式

解题思路

三段式判断：等于就记录答案并跳出；小了往右找；大了往左找。ans 初值设为「不存在」的标记——这套写法最直观，不容易死循环。

AC代码

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

int n, q;
vector<long long> a;

// 写法二：l <= r 答案记录式——命中直接记录并跳出
bool exist(long long x) {
    int l = 0, r = n - 1, ans = -1;
    while (l <= r) {
        int mid = (l + r) / 2;
        if (a[mid] == x) { ans = mid; break; }     // 命中：记录答案
        if (a[mid] < x) l = mid + 1;
        else r = mid - 1;
    }
    return ans != -1;
}

int main() {
    cin >> n >> q;
    a.resize(n);
    for (auto& x : a) cin >> x;
    while (q--) {
        long long x;
        cin >> x;
        cout << (exist(x) ? "YES" : "NO") << "\n";
    }
    return 0;
}
写法三：递归实现（两种形式）

解题思路

把循环改写成递归：existLR 对应收敛式（区间缩到一点），existAns 对应答案记录式（命中返回下标）。递归深度只有 \(\log n\) 层，不会爆栈。

AC代码

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

int n, q;
vector<long long> a;

// 递归形式一（对应 l < r 收敛式）
bool existLR(int l, int r, long long x) {
    if (l >= r) return a[l] == x;
    int mid = (l + r) / 2;
    if (a[mid] < x) return existLR(mid + 1, r, x);
    return existLR(l, mid, x);
}

// 递归形式二（对应 l <= r 答案记录式）
long long existAns(int l, int r, long long x) {
    if (l > r) return -1;
    int mid = (l + r) / 2;
    if (a[mid] == x) return mid;
    if (a[mid] < x) return existAns(mid + 1, r, x);
    return existAns(l, mid - 1, x);
}

int main() {
    cin >> n >> q;
    a.resize(n);
    for (auto& x : a) cin >> x;
    while (q--) {
        long long x;
        cin >> x;
        cout << (existLR(0, n - 1, x) ? "YES" : "NO") << "\n";
    }
    return 0;
}

二分查找模板：左边界（三种写法）2

二分查找：左边界

题目描述

给出一个升序数组（下标从 1 开始），\(q\) 次询问。对每次询问的数 \(x\)，输出第一个大于等于 \(x\) 的元素的下标，具体分三种情况：

  1. 数组中存在等于 \(x\) 的数：输出 \(x\) 第一次出现的下标；
  2. 数组中不存在等于 \(x\) 的数，但存在大于 \(x\) 的数：输出第一个大于 \(x\) 的元素的下标（也就是把 \(x\) 插进数组后，它应该待的位置）；
  3. 所有元素都小于 \(x\)：输出 \(n + 1\)。

这三种情况合起来就是「第一个 \(\ge x\) 的下标」——正是 STL 中 lower_bound 的语义。

输入格式

第一行两个整数 \(n, q\)；第二行 \(n\) 个升序整数；接下来 \(q\) 行每行一个询问 \(x\)。

输出格式

共 \(q\) 行，每行一个位置。

样例输入

1
2
3
4
5
6
5 4
1 3 3 5 7
3
4
0
8

样例输出

1
2
3
4
2
4
1
6

（四个询问正好对应三种情况：3 存在，输出第一次出现的下标 2；4 不存在但有更大的，输出第一个大于它的下标 4；0 不存在，第一个 ≥ 0 的是下标 1；所有数都 < 8，输出 n+1 = 6。）

数据范围

  • \(1 \le n, q \le 10^5\)
  • 数组元素与询问绝对值 \(\le 10^9\)

⬇ 点击下载数据包

写法一：l < r 收敛式

解题思路

a[mid] < x 时答案一定在右侧（l = mid + 1），否则答案可能是 mid（r = mid）——区间收缩到一点即「第一个 \(\ge x\)」的位置。

AC代码

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

int n, q;
vector<long long> a;

// 写法一：l < r 收敛式——退出时 l 是「第一个 >= x」的位置（不存在则 l = n）
int leftBound(long long x) {
    int l = 0, r = n - 1;
    while (l < r) {
        int mid = (l + r) / 2;
        if (a[mid] < x) l = mid + 1;
        else r = mid;
    }
    return a[l] >= x ? l + 1 : n + 1;          // 转成 1-based；都小于 x 则 n+1
}

int main() {
    cin >> n >> q;
    a.resize(n);
    for (auto& x : a) cin >> x;
    while (q--) {
        long long x;
        cin >> x;
        cout << leftBound(x) << "\n";
    }
    return 0;
}
写法二：l <= r + answer 记录式

解题思路

a[mid] >= x 时 mid 是一个可行答案，记录下来（ans = mid）并继续向左压（r = mid - 1）看有没有更靠前的；否则向右找。

AC代码

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

int n, q;
vector<long long> a;

// 写法二：l <= r 答案记录式——满足条件就记录下标并继续向左压缩
int leftBound(long long x) {
    int l = 0, r = n - 1, ans = n + 1;         // 初值 n+1：都小于 x 时输出 n+1
    while (l <= r) {
        int mid = (l + r) / 2;
        if (a[mid] >= x) { ans = mid + 1; r = mid - 1; }
        else l = mid + 1;
    }
    return ans;
}

int main() {
    cin >> n >> q;
    a.resize(n);
    for (auto& x : a) cin >> x;
    while (q--) {
        long long x;
        cin >> x;
        cout << leftBound(x) << "\n";
    }
    return 0;
}
写法三：递归实现

解题思路

收敛式的递归版：区间缩到一点时返回位置。递归深度 \(\log n\)。

AC代码

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

int n, q;
vector<long long> a;

// 递归形式一（对应 l < r 收敛式）：返回第一个 >= x 的 0-based 下标
int leftLR(int l, int r, long long x) {
    if (l >= r) return l;
    int mid = (l + r) / 2;
    if (a[mid] < x) return leftLR(mid + 1, r, x);
    return leftLR(l, mid, x);
}

int main() {
    cin >> n >> q;
    a.resize(n);
    for (auto& x : a) cin >> x;
    while (q--) {
        long long x;
        cin >> x;
        int pos = leftLR(0, n - 1, x);
        cout << (a[pos] >= x ? pos + 1 : n + 1) << "\n";
    }
    return 0;
}

二分查找模板：右边界（三种写法）3

二分查找：右边界

题目描述

给出一个升序数组（下标从 1 开始），\(q\) 次询问。对每次询问的数 \(x\)，输出最后一个小于等于 \(x\) 的元素的下标，同样分三种情况：

  1. 数组中存在等于 \(x\) 的数：输出 \(x\) 最后一次出现的下标；
  2. 数组中不存在等于 \(x\) 的数，但存在小于 \(x\) 的数：输出最后一个小于 \(x\) 的元素的下标；
  3. 所有元素都大于 \(x\)：输出 \(0\)。

合起来就是「最后一个 \(\le x\) 的下标」——STL 中 upper_bound(x) - 1 的语义。

输入格式

第一行两个整数 \(n, q\)；第二行 \(n\) 个升序整数；接下来 \(q\) 行每行一个询问 \(x\)。

输出格式

共 \(q\) 行，每行一个位置。

样例输入

1
2
3
4
5
6
5 4
1 3 3 5 7
3
4
8
0

样例输出

1
2
3
4
3
3
5
0

（四种情况：3 存在，输出最后一次出现的下标 3；4 不存在但有更小的，输出最后一个小于它的下标 3；所有数 ≤ 8，最后一个在下标 5；所有数都 > 0，输出 0。）

数据范围

  • \(1 \le n, q \le 10^5\)
  • 数组元素与询问绝对值 \(\le 10^9\)

⬇ 点击下载数据包

写法一：l < r 收敛式

解题思路

与左边界镜像：a[mid] <= x 时答案可能是 mid 或在右侧（l = mid），否则在左侧（r = mid - 1）。命门：mid 必须上取整 (l + r + 1) / 2，否则 l = mid 会死循环。

AC代码

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

int n, q;
vector<long long> a;

// 写法一：l < r 收敛式——注意 mid 取 (l+r+1)/2 上取整，否则 l=mid 会死循环
int rightBound(long long x) {
    int l = 0, r = n - 1;
    while (l < r) {
        int mid = (l + r + 1) / 2;             // 上取整是右边界写法的命门
        if (a[mid] <= x) l = mid;
        else r = mid - 1;
    }
    return a[l] <= x ? l + 1 : 0;              // 转 1-based；都大于 x 则 0
}

int main() {
    cin >> n >> q;
    a.resize(n);
    for (auto& x : a) cin >> x;
    while (q--) {
        long long x;
        cin >> x;
        cout << rightBound(x) << "\n";
    }
    return 0;
}
写法二：l <= r + answer 记录式

解题思路

a[mid] <= x 时 mid 是可行答案，记录后继续向右压（l = mid + 1）找更靠后的；否则向左找。ans 初值 0 表示「所有数都大于 x」。

AC代码

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

int n, q;
vector<long long> a;

// 写法二：l <= r 答案记录式——满足条件记录下标并继续向右压缩
int rightBound(long long x) {
    int l = 0, r = n - 1, ans = 0;             // 初值 0：都大于 x 时输出 0
    while (l <= r) {
        int mid = (l + r) / 2;
        if (a[mid] <= x) { ans = mid + 1; l = mid + 1; }
        else r = mid - 1;
    }
    return ans;
}

int main() {
    cin >> n >> q;
    a.resize(n);
    for (auto& x : a) cin >> x;
    while (q--) {
        long long x;
        cin >> x;
        cout << rightBound(x) << "\n";
    }
    return 0;
}
写法三：递归实现

解题思路

递归答案记录式：先向右半段找（可能有更靠后的可行解），右边没有才用当前 mid。

AC代码

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

int n, q;
vector<long long> a;

// 递归形式二（对应 l <= r 答案记录式）：返回最后一个 <= x 的 0-based 下标，无则 -1
int rightAns(int l, int r, long long x) {
    if (l > r) return -1;
    int mid = (l + r) / 2;
    if (a[mid] <= x) {
        int res = rightAns(mid + 1, r, x);     // 右边可能还有更靠后的
        return res != -1 ? res : mid;
    }
    return rightAns(l, mid - 1, x);
}

int main() {
    cin >> n >> q;
    a.resize(n);
    for (auto& x : a) cin >> x;
    while (q--) {
        long long x;
        cin >> x;
        int pos = rightAns(0, n - 1, x);
        cout << (pos == -1 ? 0 : pos + 1) << "\n";
    }
    return 0;
}

出现次数4

出现次数

题目描述

给出一个升序数组，\(q\) 次询问：数 \(x\) 在数组中出现了多少次。

输入格式

第一行两个整数 \(n, q\)；第二行 \(n\) 个升序整数；接下来 \(q\) 行每行一个询问 \(x\)。

输出格式

共 \(q\) 行，每行一个整数，为 \(x\) 的出现次数。

样例输入

1
2
3
4
5
10 3
1 3 3 3 5 5 7 7 7 9
3
7
4

样例输出

1
2
3
3
3
0

数据范围

  • \(1 \le n, q \le 10^5\)
  • 数组元素与询问绝对值 \(\le 10^9\)

⬇ 点击下载数据包

出现次数 AC 代码

解题思路

用前面两个模板组合：设 \(L\) = 左边界（第一个 \(\ge x\) 的下标）、\(R\) = 右边界（最后一个 \(\le x\) 的下标），出现次数 \(= R - L + 1\)；\(L > R\) 说明 \(x\) 不存在，次数为 0。

AC代码

 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;

int n, q;
vector<long long> a;

// 第一个 >= x 的 0-based 下标
int leftBound(long long x) {
    int l = 0, r = n - 1;
    while (l < r) {
        int mid = (l + r) / 2;
        if (a[mid] < x) l = mid + 1;
        else r = mid;
    }
    return a[l] >= x ? l : n;
}

// 最后一个 <= x 的 0-based 下标
int rightBound(long long x) {
    int l = 0, r = n - 1;
    while (l < r) {
        int mid = (l + r + 1) / 2;
        if (a[mid] <= x) l = mid;
        else r = mid - 1;
    }
    return a[l] <= x ? l : -1;
}

int main() {
    cin >> n >> q;
    a.resize(n);
    for (auto& x : a) cin >> x;
    while (q--) {
        long long x;
        cin >> x;
        int L = leftBound(x), R = rightBound(x);
        cout << (L > R ? 0 : R - L + 1) << "\n";   // 左边界越过右边界 = 不存在
    }
    return 0;
}

查找位置5

查找位置

题目描述

给出一个升序数组，\(q\) 次询问：若 \(x\) 在数组中，输出它第一次出现的位置（下标从 1 开始）；否则输出 -1。

输入格式

第一行两个整数 \(n, q\)；第二行 \(n\) 个升序整数；接下来 \(q\) 行每行一个询问 \(x\)。

输出格式

共 \(q\) 行，每行一个位置或 -1。

样例输入

1
2
3
4
6 2
1 3 5 7 9 11
7
4

样例输出

1
2
4
-1

数据范围

  • \(1 \le n, q \le 10^5\)
  • 数组元素与询问绝对值 \(\le 10^9\)，且数组元素互不相同

⬇ 点击下载数据包

查找位置 AC 代码

解题思路

l <= r + answer 记录式的标准应用：命中即记录位置并跳出循环，循环结束 ans 仍为 -1 说明不存在。

AC代码

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

int n, q;
vector<long long> a;

int main() {
    cin >> n >> q;
    a.resize(n);
    for (auto& x : a) cin >> x;
    while (q--) {
        long long x;
        cin >> x;
        // l <= r 答案记录式：存在输出下标（1-based），不存在输出 -1
        int l = 0, r = n - 1, ans = -1;
        while (l <= r) {
            int mid = (l + r) / 2;
            if (a[mid] == x) { ans = mid + 1; break; }
            if (a[mid] < x) l = mid + 1;
            else r = mid - 1;
        }
        cout << ans << "\n";
    }
    return 0;
}

值域二分：第 k 小6

值域二分：第 k 小

题目描述

输入 \(n\) 个正整数（不去重），输出其中第 \(k\) 小的数。要求用在值域上二分的方法完成。

输入格式

第一行两个整数 \(n, k\)；第二行 \(n\) 个正整数。

输出格式

一个整数，为第 \(k\) 小的数。

样例输入

1
2
5 3
30 10 20 30 25

样例输出

1
25

数据范围

  • \(1 \le n \le 1000\)，\(1 \le k \le n\)
  • 数值为不超过 \(10^5\) 的正整数

⬇ 点击下载数据包

值域二分 AC 代码

解题思路

不排数组，而是对答案的取值范围（值域 [1, 10⁵]）二分：「不超过 \(v\) 的数有 \(count(v)\) 个」，\(count\) 随 \(v\) 增大单调不减——找最小的 \(v\) 使 \(count(v) \ge k\)。这就是二分答案的雏形。

AC代码

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

int n, k;
vector<long long> a;

// 值不超过 v 的数的个数
long long countLE(long long v) {
    long long c = 0;
    for (long long x : a)
        if (x <= v) c++;
    return c;
}

int main() {
    cin >> n >> k;
    a.resize(n);
    for (auto& x : a) cin >> x;
    // 在值域 [1, 1e5] 上二分答案：找最小的 v 使 count(<=v) >= k
    long long lo = 1, hi = 100000;
    while (lo < hi) {
        long long mid = (lo + hi) / 2;
        if (countLE(mid) >= k) hi = mid;       // mid 够用：答案在 [lo, mid]
        else lo = mid + 1;                     // 不够：答案在 [mid+1, hi]
    }
    cout << lo << "\n";
    return 0;
}

实数二分

求平方根7

求平方根

题目描述

输入一个非负实数 \(x\)，输出 \(\sqrt{x}\)，精确到小数点后 6 位。要求用实数二分实现（分别给出两种收敛写法）。

输入格式

一个非负实数 \(x\)。

输出格式

\(\sqrt{x}\)，保留 6 位小数。

样例输入

1
2

样例输出

1
1.414214

数据范围

  • \(0 \le x \le 10^9\)

⬇ 点击下载数据包

写法一：eps 收敛

解题思路

实数二分没有「退出时 l=r」的概念，用区间长度控制精度：\(hi - lo < 10^{-8}\) 时停止。上界取 \(\max(1, x)\) 兼容 \(x < 1\) 的情况。

AC代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
#include <bits/stdc++.h>
using namespace std;

int main() {
    double x;
    cin >> x;
    // 写法一：eps 收敛——区间长度小于 1e-8 时停止
    double lo = 0, hi = max(1.0, x);
    while (hi - lo > 1e-8) {
        double mid = (lo + hi) / 2;
        if (mid * mid < x) lo = mid;
        else hi = mid;
    }
    printf("%.6f\n", lo);
    return 0;
}
写法二：固定迭代 100 次

解题思路

每次迭代区间减半，100 次后区间缩到 \(2^{-100}\) 倍——远超所需精度，且不怕 eps 设错导致死循环。竞赛中更常用。

AC代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
#include <bits/stdc++.h>
using namespace std;

int main() {
    double x;
    cin >> x;
    // 写法二：固定迭代 100 次——不依赖 eps，同样收敛到精度极限
    double lo = 0, hi = max(1.0, x);
    for (int i = 0; i < 100; i++) {
        double mid = (lo + hi) / 2;
        if (mid * mid < x) lo = mid;
        else hi = mid;
    }
    printf("%.6f\n", lo);
    return 0;
}

求立方根23

求立方根

题目描述

输入一个实数 \(x\)（可能是负数），输出 \(\sqrt[3]{x}\)，精确到小数点后 6 位。要求用实数二分实现。

输入格式

一个实数 \(x\)。

输出格式

\(\sqrt[3]{x}\)，保留 6 位小数。

样例输入

1
27

样例输出

1
3.000000

数据范围

  • \(-10^9 \le x \le 10^9\)

⬇ 点击下载数据包

求立方根 AC 代码

解题思路

与求平方根成对：立方函数同样单调，区间长度减半 100 次即可。负数是本题新边界——负数的立方根没有定义在 \([0, hi]\) 上，先把符号摘出来，在 \(|x|\) 上二分，最后把符号贴回去；上界同样取 \(\max(1, |x|)\) 兼容 \(|x| < 1\)。

AC代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
#include <bits/stdc++.h>
using namespace std;

int main() {
    double x;
    cin >> x;
    // 立方根对负数也有定义：先把符号摘出来，在 |x| 上二分，最后贴回符号
    int sign = 1;
    if (x < 0) { sign = -1; x = -x; }
    double lo = 0, hi = max(1.0, x);
    for (int i = 0; i < 100; i++) {
        double mid = (lo + hi) / 2;
        if (mid * mid * mid < x) lo = mid;
        else hi = mid;
    }
    printf("%.6f\n", sign * lo);
    return 0;
}

一元三次方程求解8

一元三次方程求解

题目描述

有方程 \(ax^3 + bx^2 + cx + d = 0\)，已知它存在三个不同实根，根都在 \([-100, 100]\) 内，且根与根之差的绝对值 \(\ge 1\)。从小到大输出这三个根，精确到小数点后 2 位。提示：若 \(f(x_1) \cdot f(x_2) < 0\)，则 \((x_1, x_2)\) 之间必有根。

输入格式

一行四个实数 \(a, b, c, d\)。

输出格式

一行三个实根，用空格分隔，保留 2 位小数。

样例输入

1
1 -5 -4 20

样例输出

1
-2.00 2.00 5.00

数据范围

  • \(a, b, c, d\) 均为绝对值不超过 100 的实数
一元三次方程求解 AC 代码

解题思路

「根与根之差 ≥ 1」保证每段长度为 1 的区间 \([x, x+1]\) 内最多一个根——从 \(-100\) 到 \(100\) 枚举每个单位区间，若端点函数值异号（或端点恰为零）就实数二分求出根；用秦九韶格式计算 \(f(x)\)。

AC代码

 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;

double a, b, c, d;

double f(double x) {
    return ((a * x + b) * x + c) * x + d;      // 秦九韶格式，避免手算幂
}

int main() {
    cin >> a >> b >> c >> d;
    int cnt = 0;
    // 根与根之差 >= 1：枚举每一段 [x, x+1]，段内最多一个根
    for (double x = -100; x < 100 && cnt < 3; x += 1) {
        double l = x, r = x + 1;
        if (f(l) == 0) {                       // 恰好在端点上
            printf("%.2f ", l);
            cnt++;
            continue;
        }
        if (f(l) * f(r) < 0) {                 // 异号 → 段内有根，实数二分
            double lo = l, hi = r, mid;
            while (hi - lo > 1e-6) {
                mid = (lo + hi) / 2;
                if (f(lo) * f(mid) <= 0) hi = mid;
                else lo = mid;
            }
            printf("%.2f ", lo);
            cnt++;
        }
    }
    return 0;
}

银行贷款9

银行贷款

题目描述

从银行贷款 \(w_0\) 元，之后每月偿还固定金额 \(w\) 元，共 \(m\) 个月还清（按月计息）。求月利率（用百分数表示），四舍五入精确到 \(0.1\%\)。

输入格式

一行三个正整数 \(w_0, w, m\)。

输出格式

一个实数，为月利率的百分数值（保留一位小数）。

样例输入

1
1000 100 12

样例输出

1
2.9

数据范围

  • \(1 \le w_0, w \le 2^{31} - 1\)，\(1 \le m \le 3000\)
  • 数据保证答案不超过 \(300.0\%\)
银行贷款 AC 代码

解题思路

「多大的利率恰好 \(m\) 个月还清」——月利率越大欠得越多，具有单调性，二分答案：对候选利率模拟 \(m\) 个月还款（\(bal = bal \times (1+r) - w\)），余额大于 0 说明利率偏高，调小；否则调大。

AC代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
#include <bits/stdc++.h>
using namespace std;

int main() {
    double w0, w;
    long long m;
    cin >> w0 >> w >> m;
    // 二分月利率 r（百分数 0 ~ 300%）：利率越大，还完所需的钱越多
    double lo = 0, hi = 3.0;                   // 月利率上限 300%（即 3.0）
    while (hi - lo > 1e-9) {
        double mid = (lo + hi) / 2;
        double bal = w0;
        for (int i = 0; i < m; i++) bal = bal * (1 + mid) - w;   // 模拟还款
        if (bal > 0) hi = mid;                 // 欠得多 → 利率太大
        else lo = mid;                         // 已还清 → 利率还可更大
    }
    printf("%.1f\n", lo * 100);                // 转成百分数，保留一位小数
    return 0;
}

单调函数零点24

单调函数零点

题目描述

已知函数 \(f(x) = x^3 + ax + b\)，其中 \(1 \le a\)，导数 \(3x^2 + a > 0\) 保证 \(f\) 严格单调递增，且零点必在 \([-100, 100]\) 内。用实数二分求出这个零点，保留 6 位小数。

输入格式

一行两个整数 \(a, b\)。

输出格式

一个实数，为零点，保留 6 位小数。

样例输入

1
1 1

样例输出

1
-0.682328

数据范围

  • \(1 \le a \le 1000\)
  • \(-10^4 \le b \le 10^4\)

⬇ 点击下载数据包

单调函数零点 AC 代码

解题思路

与「一元三次方程求解」的区别：那题 \(f\) 不单调、要枚举区间找三个根；本题 \(f\) 全程单调、零点唯一，直接在 \([-100, 100]\) 上二分——\(f(mid) < 0\) 零点在右，否则在左。端点合法性由数据范围保证：\(f(-100) < 0 < f(100)\)。

AC代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <bits/stdc++.h>
using namespace std;

double a, b;

double f(double x) {
    return x * x * x + a * x + b;
}

int main() {
    cin >> a >> b;
    // 导数 3x^2 + a > 0 保证严格单调递增，零点唯一
    double lo = -100, hi = 100;
    for (int i = 0; i < 100; i++) {
        double mid = (lo + hi) / 2;
        if (f(mid) < 0) lo = mid;
        else hi = mid;
    }
    // 根恰好为 0 时 lo 可能收敛到 -1e-28，会被打印成 -0.000000，归一成 0
    if (fabs(lo) < 1e-7) lo = 0;
    printf("%.6f\n", lo);
    return 0;
}

二分答案 · 最大化最小值

木材加工10

木材加工

题目描述

木材厂有 \(n\) 根原木，第 \(i\) 根长度为 \(L_i\)。现在要把这些原木切成等长的正整数长度小段（每根原木只能切不能再拼，切下长度不足 1 的余料丢弃），要求切出至少 \(k\) 段。求单段长度的最大值。

输入格式

第一行两个整数 \(n, k\)。接下来 \(n\) 行，每行一个整数 \(L_i\)。

输出格式

一个整数，单段长度的最大值；如果连长度为 1 都切不出 \(k\) 段，输出 0。

样例输入

1
2
3
4
3 7
10
24
15

样例输出

1
6

（长度 6：10 切 1 段、24 切 4 段、15 切 2 段，共 7 段；长度 7 只能切出 6 段。）

数据范围

  • \(1 \le n \le 10^5\)，\(1 \le k \le 10^9\)
  • \(1 \le L_i \le 10^9\)
木材加工 AC 代码

解题思路

二分答案。段长 \(x\) 越大，能切出的总段数 \(\sum \lfloor L_i/x \rfloor\) 越少，具有单调性；二分 \(x\)，判定「总段数 \(\ge k\)」是否成立，求满足条件的最大 \(x\)。

AC代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
#include <bits/stdc++.h>
using namespace std;

int main() {
    int n;
    long long k;
    cin >> n >> k;
    vector<long long> L(n);
    for (auto& x : L) cin >> x;
    // 二分答案：段长 x 越大切出的段数越少，check 单调
    long long lo = 1, hi = *max_element(L.begin(), L.end()), ans = 0;
    while (lo <= hi) {
        long long mid = (lo + hi) / 2, cnt = 0;
        for (long long v : L) cnt += v / mid;
        if (cnt >= k) { ans = mid; lo = mid + 1; }
        else hi = mid - 1;
    }
    cout << ans << "\n";                   // 连长度 1 都凑不够 k 段时 ans = 0
    return 0;
}

砍树11

砍树

题目描述

伐木机设置一个高度参数 \(H\)，锯掉所有高于 \(H\) 的部分。\(n\) 棵树高度为 \(h_i\)，需要总共砍到至少 \(M\) 米木材。求锯片最大的整数高度 \(H\)（再高 1 米就砍不够 \(M\) 米）。

输入格式

第一行两个整数 \(N, M\)；第二行 \(N\) 个整数表示树高。

输出格式

一个整数，为锯片的最高高度。

样例输入

1
2
5 20
4 42 40 26 46

样例输出

1
36

（\(H = 36\) 时能砍到 \(6 + 4 + 10 = 20\) 米；再高就不足 20 米。）

数据范围

  • \(1 \le N \le 10^6\)，\(1 \le M \le 2 \times 10^9\)，树高 \(\le 4 \times 10^5\)
砍树 AC 代码

解题思路

二分答案。\(H\) 越大砍到的木材越少，check 随 \(H\) 递减——与木材加工的方向正好相反，练「二分方向辨析」。木材总量要开 long long。

AC代码

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

int n, m;
vector<long long> h;

// 锯片高度为 H 时能砍到的木材总量
long long wood(long long H) {
    long long s = 0;
    for (long long x : h)
        if (x > H) s += x - H;
    return s;
}

int main() {
    cin >> n >> m;
    h.resize(n);
    for (auto& x : h) cin >> x;
    long long lo = 0, hi = *max_element(h.begin(), h.end());
    while (lo < hi) {
        long long mid = (lo + hi + 1) / 2;     // 上取整：求最大可行 H
        if (wood(mid) >= m) lo = mid;          // 够砍：还能更高
        else hi = mid - 1;
    }
    cout << lo << "\n";
    return 0;
}

跳石头12

跳石头

题目描述

起点与终点相距 \(L\)，河道中有 \(n\) 块石头，第 \(i\) 块距起点 \(a_i\)。运动员从起点出发，每步跳到相邻的下一块石头，最后跳到终点。现在可以挪走至多 \(m\) 块石头（起点和终点不可挪），求跳跃过程中最小跳距的最大值。

输入格式

第一行三个整数 \(L, n, m\)。接下来 \(n\) 行，每行一个整数 \(a_i\)（保证递增且 \(a_i < L\)）。

输出格式

一个整数，最小跳距的最大值。

样例输入

1
2
3
4
5
6
25 5 2
2
11
14
17
21

样例输出

1
4

（挪走距起点 2 和 14 的两块石头。）

数据范围

  • \(1 \le L \le 10^9\)
  • \(0 \le m \le n \le 5 \times 10^4\)
  • \(1 \le a_i < L\)
跳石头 AC 代码

解题思路

二分答案 + 贪心判定。最小跳距 \(d\) 越大，需要挪走的石头越多，具有单调性；从起点向终点扫描，当前石头与立足点距离 \(< d\) 就挪走它，统计挪走总数是否 \(\le m\)。

AC代码

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

int main() {
    long long L;
    int n, m;
    cin >> L >> n >> m;
    vector<long long> a(n + 2);
    a[0] = 0;
    a[n + 1] = L;
    for (int i = 1; i <= n; i++) cin >> a[i];
    // 二分答案 d：贪心检查——从起点出发，相邻间距不足 d 就挪走当前石头
    auto ok = [&](long long d) {
        int cnt = 0, cur = 0;              // cur = 当前立足点下标
        for (int i = 1; i <= n + 1; i++) {
            if (a[i] - a[cur] < d) cnt++;
            else cur = i;
        }
        return cnt <= m;
    };
    long long lo = 0, hi = L, ans = 0;
    while (lo <= hi) {
        long long mid = (lo + hi) / 2;
        if (ok(mid)) { ans = mid; lo = mid + 1; }
        else hi = mid - 1;
    }
    cout << ans << "\n";
    return 0;
}

进击的奶牛13

进击的奶牛

题目描述

直线上有 \(n\) 个牛舍位置 \(x_i\)，把 \(m\) 头牛放进牛舍，使任意两头牛之间的最小距离尽可能大。求这个最大的最小距离。

输入格式

第一行两个整数 \(n, m\)；下面 \(n\) 行每行一个位置 \(x_i\)（不保证递增）。

输出格式

一行一个整数，为最大的最小距离。

样例输入

1
2
3
4
5
6
5 3
1
2
8
4
9

样例输出

1
3

（把牛放在 1、4、8 三个位置，最小距离 3。）

数据范围

  • \(2 \le n \le 10^5\)，\(2 \le m \le n\)，\(0 \le x_i \le 10^9\)
进击的奶牛 AC 代码

解题思路

二分答案 + 贪心判定。与跳石头互为镜像：跳石头数「要挪走的」，奶牛数「能放下的」——check 函数一个累计必须挪走数、一个贪心放置数，方向相反结构相同。注意先排序（数据不保证单调）。

AC代码

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

int n, m;
vector<long long> x;

// 最小间距为 d 时，贪心放牛能放多少头
int place(long long d) {
    int cnt = 1, last = 0;                     // 第一头放第一间
    for (int i = 1; i < n; i++)
        if (x[i] - x[last] >= d) { cnt++; last = i; }
    return cnt;
}

int main() {
    cin >> n >> m;
    x.resize(n);
    for (auto& v : x) cin >> v;
    sort(x.begin(), x.end());                  // 不保证单调，先排序
    long long lo = 1, hi = x[n - 1] - x[0];
    while (lo < hi) {
        long long mid = (lo + hi + 1) / 2;
        if (place(mid) >= m) lo = mid;         // 放得下 m 头：间距还能更大
        else hi = mid - 1;
    }
    cout << lo << "\n";
    return 0;
}

二分答案 · 最小化最大值

数列分段 Section II14

数列分段 Section II

题目描述

把长度为 \(N\) 的正整数数列分成 \(M\) 段（每段连续），使每段和的最大值最小。例如数列 4 2 4 5 1 分成 3 段：[4 2][4 5][1] 的最大段和为 9，而 [4][2 4][5 1] 的最大段和只有 6——后者更优。求这个最小的最大段和。

输入格式

第一行两个正整数 \(N, M\)；第二行 \(N\) 个非负整数。

输出格式

一个正整数，为最小的最大段和。

样例输入

1
2
5 3
4 2 4 5 1

样例输出

1
6

数据范围

  • \(1 \le N \le 10^5\)，\(M \le N\)，\(A_i < 10^8\)，答案不超过 \(10^9\)
数列分段 Section II AC 代码

解题思路

二分答案·最小化最大值：段和上限 \(lim\) 越大需要的段数越少。check 从左到右贪心装段，统计段数是否 \(\le M\)；下界取数列最大元素（单元素超限的 \(lim\) 无解）。

AC代码

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

int n, m;
vector<long long> a;

// 段和上限为 lim 时，最少分成几段
int segments(long long lim) {
    int cnt = 1;
    long long sum = 0;
    for (long long x : a) {
        if (x > lim) return m + 1;             // 单元素超过上限：无解
        if (sum + x <= lim) sum += x;          // 还能装进当前段
        else { cnt++; sum = x; }               // 开新段
    }
    return cnt;
}

int main() {
    cin >> n >> m;
    a.resize(n);
    long long lo = 0, hi = 0;
    for (auto& x : a) {
        cin >> x;
        lo = max(lo, x);                       // 下界：最大元素（每段至少装下自己）
        hi += x;                               // 上界：全部元素之和
    }
    while (lo < hi) {
        long long mid = (lo + hi) / 2;
        if (segments(mid) <= m) hi = mid;      // 段数够少：上限还能更小
        else lo = mid + 1;
    }
    cout << lo << "\n";
    return 0;
}

最小组内极差25

最小组内极差

题目描述

给 \(n\) 个整数，把它们分成至多 \(k\) 组。先排序，再要求每组在排序后的数组中连续，最小化「组内最大值 \(-\) 组内最小值」的最大值。

输入格式

第一行两个整数 \(n, k\)；第二行 \(n\) 个整数。

输出格式

一个整数，为最小的最大组内极差。

样例输入

1
2
5 2
1 5 3 9 12

样例输出

1
4

（排序后为 1 3 5 9 12，分成 [1 3 5][9 12]，极差分别为 4 和 3。）

数据范围

  • \(2 \le n \le 100\)
  • \(1 \le k \le n\)
  • \(1 \le a_i \le 10^9\)

⬇ 点击下载数据包

最小组内极差 AC 代码

解题思路

排序后「连续分组」的组内极差就是两端之差。二分极差上限 \(d\)：从左扫到右，当前数与组首相差超过 \(d\) 就另起一组，统计组数是否 \(\le k\)——组数随 \(d\) 增大单调不增，标准的最小化最大值。与「数列分段 Section II」同构：把「段和」换成了「极差」，check 从前缀求和换成了减法。

AC代码

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

int n, k;
long long a[2005];

// 极差上限 d 是否可行：排序后贪心分段，组数 <= k
bool ok(long long d) {
    int groups = 1;
    long long start = a[1];
    for (int i = 2; i <= n; i++) {
        if (a[i] - start > d) {
            groups++;
            start = a[i];
        }
    }
    return groups <= k;
}

int main() {
    cin >> n >> k;
    for (int i = 1; i <= n; i++) cin >> a[i];
    sort(a + 1, a + n + 1);
    long long lo = 0, hi = a[n] - a[1];
    while (lo < hi) {
        long long mid = (lo + hi) / 2;
        if (ok(mid)) hi = mid;
        else lo = mid + 1;
    }
    cout << lo << endl;
    return 0;
}

路标设置15

路标设置

题目描述

长度为 \(L\) 的公路上原有 \(n\) 个路标（含起点和终点），相邻路标的最大距离称为「空旷指数」。最多增设 \(k\) 个路标，求能达到的最小空旷指数。

输入格式

第一行三个整数 \(L, n, k\)；第二行 \(n\) 个递增整数，为原有路标位置。

输出格式

一个整数，为最小的空旷指数。

样例输入

1
2
101 2 1
0 101

样例输出

1
51

（增设的 1 个路标放在 50 或 51 处，最大间隔为 51。）

数据范围

  • \(2 \le n \le 10^5\)，\(0 \le k \le 10^5\)，\(0 < L \le 10^7\)
路标设置 AC 代码

解题思路

二分答案·最小化最大值，与跳石头互为镜像（跳石头挪石头、这里加路标）：check 对每段长为 \(gap\) 的间隔统计需增设 \(\lceil gap / d \rceil - 1\) 个路标，总数 \(\le k\) 则 \(d\) 可行。

AC代码

 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;

long long L;
int n, k;
vector<long long> p;

// 相邻路标距离都不超过 d 时，需要的增设路标数
long long need(long long d) {
    long long cnt = 0;
    for (int i = 1; i < n; i++) {
        long long gap = p[i] - p[i - 1];
        cnt += (gap - 1) / d;                  // 每 gap 长度需增设 (gap-1)/d 个
    }
    return cnt;
}

int main() {
    cin >> L >> n >> k;
    p.resize(n);
    for (auto& v : p) cin >> v;
    long long lo = 1, hi = L;
    while (lo < hi) {
        long long mid = (lo + hi) / 2;
        if (need(mid) <= k) hi = mid;          // 增设数够用：空旷指数还能更小
        else lo = mid + 1;
    }
    cout << lo << "\n";
    return 0;
}

烘干衣服26

烘干衣服

题目描述

有 \(n\) 件衣服，第 \(i\) 件含水量为 \(a_i\)。每分钟所有衣服自然风干 1 单位；同一分钟烘干机还能选定一件衣服额外烘干 \(k\) 单位。求全部衣服含水量归零的最少分钟数。

输入格式

第一行两个整数 \(n, k\)；第二行 \(n\) 个整数 \(a_i\)。

输出格式

一个整数，为最少分钟数。

样例输入

1
2
3 2
4 6 8

样例输出

1
4

（t=4：含水量 4 自然干透；6 需要机器 1 分钟（ceil(2/2)）；8 需要机器 2 分钟（ceil(4/2)），合计 3 ≤ 4。）

数据范围

  • \(1 \le n \le 10^5\)
  • \(1 \le a_i \le 10^9\)
  • \(1 \le k \le 10^9\)

⬇ 点击下载数据包

烘干衣服 AC 代码

解题思路

二分总时间 \(t\)：一件含水量 \(a\) 的衣服自然风干 \(t\) 后还剩 \(a - t\)，每上一次烘干机（一分钟）多去 \(k\)，需要机器分钟数 \(\lceil (a-t)/k \rceil\)；所有衣服的机器分钟数之和 \(\le t\)（机器每分钟只能烘一件）即 \(t\) 可行。总需求随 \(t\) 增大单调不增，二分最小的可行 \(t\)。注意和要用 long long。

AC代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <bits/stdc++.h>
using namespace std;

int main() {
    int n;
    long long k;
    cin >> n >> k;
    vector<long long> a(n);
    long long hi = 0;
    for (auto &x : a) { cin >> x; hi = max(hi, x); }
    // t 分钟内自然晾干 1/分钟，不够的部分每件需要一次机器（一分钟烘掉 k）
    // 所需机器分钟数 = sum(ceil((a_i - t) / k))，不超过 t 即可行
    long long lo = 1;
    while (lo < hi) {
        long long mid = (lo + hi) / 2, need = 0;
        for (auto x : a)
            if (x > mid) need += (x - mid + k - 1) / k;
        if (need <= mid) hi = mid;
        else lo = mid + 1;
    }
    cout << lo << endl;
    return 0;
}

拓展 · 查找进阶

旋转数组找最小16

旋转数组找最小

题目描述

一个升序数组在某个未知点被「旋转」（如 1 2 3 4 5 变为 4 5 1 2 3）。给出旋转后的数组（元素互不相同），求其中的最小值。要求用二分完成。

输入格式

第一行一个整数 \(n\)；第二行 \(n\) 个互不相同的整数。

输出格式

一个整数，为最小值。

样例输入

1
2
7
4 5 6 7 1 2 3

样例输出

1
1

数据范围

  • \(1 \le n \le 10^5\)，元素互不相同

⬇ 点击下载数据包

旋转数组找最小 AC 代码

解题思路

关键在比较对象：拿 a[mid] 与右端点 a[r] 比——大于它说明 mid 落在旋转段（最小值在右侧），否则在有序段（最小值在 [l, mid]）。与 a[l] 比是这题的经典错误。

AC代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
#include <bits/stdc++.h>
using namespace std;

int n;
vector<long long> a;

int main() {
    cin >> n;
    a.resize(n);
    for (auto& x : a) cin >> x;
    // 旋转升序数组：与右端点 a[r] 比较（与 a[l] 比是错的——左半恒 >= a[r]）
    int l = 0, r = n - 1;
    while (l < r) {
        int mid = (l + r) / 2;
        if (a[mid] > a[r]) l = mid + 1;        // mid 在旋转段里，最小值在右侧
        else r = mid;                          // mid 在有序段里，最小值在 [l, mid]
    }
    cout << a[l] << "\n";
    return 0;
}

旋转数组找目标值27

旋转数组找目标值

题目描述

一个元素互不相同的升序数组在某个未知点被旋转（如 1 2 3 4 5 变为 4 5 1 2 3）。给出旋转后的数组和目标值 \(t\)，用二分求 \(t\) 所在的下标（从 1 开始）；不存在输出 -1。

输入格式

第一行两个整数 \(n, t\)；第二行 \(n\) 个互不相同的整数。

输出格式

一个整数，为下标或 -1。

样例输入

1
2
7 2
4 5 6 7 1 2 3

样例输出

1
6

（2 在旋转后数组的第 6 个位置。）

数据范围

  • \(1 \le n \le 10^5\)
  • 元素与目标值绝对值 \(\le 10^9\)

⬇ 点击下载数据包

旋转数组找目标值 AC 代码

解题思路

与「旋转数组找最小」成对。旋转数组从任意 mid 切开，左右两半必有一半是有序的：a[l] <= a[mid] 时左半有序，判断 \(t\) 是否落在 [a[l], a[mid]) 内，在就进左半、不在进右半；否则右半有序，对称处理。每步要么区间减半、要么直接命中，\(O(\log n)\)。

AC代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <bits/stdc++.h>
using namespace std;

int main() {
    int n, t;
    cin >> n >> t;
    vector<int> a(n + 1);
    for (int i = 1; i <= n; i++) cin >> a[i];
    int l = 1, r = n, ans = -1;
    while (l <= r) {
        int mid = (l + r) / 2;
        if (a[mid] == t) { ans = mid; break; }
        if (a[l] <= a[mid]) {          // 左半段有序
            if (a[l] <= t && t < a[mid]) r = mid - 1;
            else l = mid + 1;
        } else {                        // 右半段有序
            if (a[mid] < t && t <= a[r]) l = mid + 1;
            else r = mid - 1;
        }
    }
    cout << ans << endl;
    return 0;
}

降序数组二分17

降序数组二分

题目描述

给出一个降序数组（从大到小），\(q\) 次询问：数 \(x\) 是否在数组中。存在输出 YES，否则输出 NO。

输入格式

第一行两个整数 \(n, q\)；第二行 \(n\) 个降序整数；接下来 \(q\) 行每行一个询问 \(x\)。

输出格式

共 \(q\) 行，每行 YES 或 NO。

样例输入

1
2
3
4
5 2
9 7 5 3 1
3
4

样例输出

1
2
YES
NO

数据范围

  • \(1 \le n, q \le 10^5\)
  • 数组元素与询问绝对值 \(\le 10^9\)

⬇ 点击下载数据包

降序数组二分 AC 代码

解题思路

与升序二分唯一的区别是比较方向相反：a[mid] > x 时 \(x\) 在 mid 右侧（l = mid + 1）。照抄升序模板必错——单调方向决定比较方向。

AC代码

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

int n, q;
vector<long long> a;

int main() {
    cin >> n >> q;
    a.resize(n);
    for (auto& x : a) cin >> x;                // 数组严格降序
    while (q--) {
        long long x;
        cin >> x;
        // 降序数组：a[mid] > x 说明 x 在 mid 右侧——比较方向与升序完全相反
        int l = 0, r = n - 1, ans = -1;
        while (l <= r) {
            int mid = (l + r) / 2;
            if (a[mid] == x) { ans = mid + 1; break; }
            if (a[mid] > x) l = mid + 1;
            else r = mid - 1;
        }
        cout << (ans == -1 ? "NO" : "YES") << "\n";
    }
    return 0;
}

前驱与后继28

前驱与后继

题目描述

给出一个升序数组（可能有重复），\(q\) 次询问。对每个询问的数 \(x\)，输出它的前驱与后继：前驱 = 数组中小于 \(x\) 的最大值（不存在输出 -1）；后继 = 数组中大于 \(x\) 的最小值（不存在输出 -1）。要求用二分实现。

输入格式

第一行两个整数 \(n, q\)；第二行 \(n\) 个升序整数；接下来 \(q\) 行每行一个询问 \(x\)。

输出格式

共 \(q\) 行，每行两个整数，为前驱与后继。

样例输入

1
2
3
4
5
6
5 4
1 3 3 5 7
3
4
7
0

样例输出

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

（四行依次是：3 的前驱 1、后继 5；4 的前驱 3、后继 5；7 的前驱 5、没有后继输出 -1；0 没有前驱输出 -1、后继 1。）

数据范围

  • \(1 \le n, q \le 10^5\)
  • 数组元素与询问绝对值 \(\le 10^9\)

⬇ 点击下载数据包

前驱与后继 AC 代码

解题思路

前驱后继正是 lower_bound 与 upper_bound 的直接应用：前驱 = 第一个 \(\ge x\) 的位置左边那个（它左边的全都 \(< x\)）；后继 = 第一个 \(> x\) 位置上的值。等于 \(x\) 的元素被两个界夹在中间，正好都不算——这就是「严格小于 / 严格大于」的模板写法，别在循环里写 a[mid] < x 之外的特殊判断。

AC代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
#include <bits/stdc++.h>
using namespace std;

int main() {
    int n, q;
    cin >> n >> q;
    vector<int> a(n + 1);
    for (int i = 1; i <= n; i++) cin >> a[i];
    while (q--) {
        int x;
        cin >> x;
        // 前驱 = 第一个 >= x 的位置左边那个（左边全是 < x）
        int lb = lower_bound(a.begin() + 1, a.end(), x) - a.begin();
        int pred = (lb >= 2 ? a[lb - 1] : -1);
        // 后继 = 第一个 > x 的位置（upper_bound）
        int ub = upper_bound(a.begin() + 1, a.end(), x) - a.begin();
        int succ = (ub <= n ? a[ub] : -1);
        cout << pred << " " << succ << endl;
    }
    return 0;
}

两个有序数组的第 k 小29

两个有序数组的第 k 小

题目描述

给出两个升序数组（长度分别为 \(n, m\)）与整数 \(k\)，输出把两数组合并后（重复元素照常计入）的第 \(k\) 小的数。要求不排序，用归并扫描实现。

输入格式

第一行三个整数 \(n, m, k\)；第二行 \(n\) 个升序整数；第三行 \(m\) 个升序整数。

输出格式

一个整数，为第 \(k\) 小的数。

样例输入

1
2
3
4 3 5
1 3 5 7
2 4 6

样例输出

1
5

（合并后为 1 2 3 4 5 6 7，第 5 个是 5。）

数据范围

  • \(1 \le n, m \le 10^5\)
  • \(1 \le k \le n + m\)
  • 元素绝对值 \(\le 10^9\)

⬇ 点击下载数据包

两个有序数组的第 k 小 AC 代码

解题思路

归并思想：两队各自队首是当前最小，每次吐出较小的队首，吐 \(k\) 次就是答案。比较时写 a[i] <= b[j] 保证稳定性（相等时先吐 A 队，结果不受影响）。这是手写归并排序的内核——L23 排序课的「归并」在查找场景的回归。

AC代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
#include <bits/stdc++.h>
using namespace std;

int main() {
    int n, m;
    long long k;
    cin >> n >> m >> k;
    vector<int> a(n), b(m);
    for (auto &x : a) cin >> x;
    for (auto &x : b) cin >> x;
    // 归并扫描：每次吐出两队队首中较小的一个，第 k 个吐出的就是答案
    int i = 0, j = 0;
    long long cnt = 0, ans = 0;
    while (cnt < k) {
        if (j >= m || (i < n && a[i] <= b[j])) ans = a[i++];
        else ans = b[j++];
        cnt++;
    }
    cout << ans << endl;
    return 0;
}

杨氏矩阵查找30

杨氏矩阵查找

题目描述

给定 \(n \times m\) 的矩阵，每行从左到右非降、每列从上到下非降（杨氏矩阵）。\(q\) 次询问：数 \(x\) 是否在矩阵中。要求单次询问复杂度 \(O(n + m)\)。

输入格式

第一行三个整数 \(n, m, q\)；接下来 \(n\) 行每行 \(m\) 个整数；最后 \(q\) 行每行一个询问 \(x\)。

输出格式

共 \(q\) 行，每行 YES 或 NO。

样例输入

1
2
3
4
5
6
7
3 4 3
1 4 7 11
2 5 8 12
3 6 9 16
5
10
16

样例输出

1
2
3
YES
NO
YES

数据范围

  • \(1 \le n, m \le 500\)
  • \(1 \le q \le 500\)
  • \(0 \le\) 矩阵元素与询问 \(\le 10^9\)

⬇ 点击下载数据包

杨氏矩阵查找 AC 代码

解题思路

从右上角出发：当前值比 \(x\) 大，这一列下面只会更大，往左走排除一列；比 \(x\) 小，这一行左边只会更小，往下走排除一行。每步排除一整行或一整列，最多 \(n + m\) 步。从左上角出发是经典错误——两个方向都可能走，无法决策。

AC代码

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

int a[1005][1005];

int main() {
    int n, m, q;
    cin >> n >> m >> q;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++) cin >> a[i][j];
    while (q--) {
        int x;
        cin >> x;
        // 从右上角出发：比 x 大往左，比 x 小往下，每步排除一行或一列
        int i = 1, j = m;
        bool found = false;
        while (i <= n && j >= 1) {
            if (a[i][j] == x) { found = true; break; }
            if (a[i][j] > x) j--;
            else i++;
        }
        cout << (found ? "YES" : "NO") << endl;
    }
    return 0;
}

三分求极值

【模板】三分法18

【模板】三分法

题目描述

给定一个 \(N\) 次函数，保证在 \([l, r]\) 内存在一点 \(x_0\)，使函数在 \([l, x_0]\) 上单调增、\([x_0, r]\) 上单调减（单峰）。用三分法求出峰值点 \(x_0\)（误差不超过 \(10^{-5}\)）。

输入格式

第一行一个正整数 \(N\) 和两个实数 \(l, r\)；第二行 \(N+1\) 个实数，从高次到低次为各项系数。

输出格式

一行一个实数，为峰值点横坐标（保留 5 位小数）。

样例输入

1
2
3 -0.9981 0.5
1 -3 -3 1

样例输出

1
-0.41421

数据范围

  • \(6 \le N \le 13\)，系数与 \(l, r\) 绝对值 \(\le 100\)
三分法 AC 代码

解题思路

每次取区间内两个三分点 \(m_1 = l + (r-l)/3\)、\(m_2 = r - (r-l)/3\)，比较函数值：求峰值时值小的那一侧一定不含峰——\(f(m_1) < f(m_2)\) 就舍弃 \([l, m_1]\)，否则舍弃 \([m_2, r]\)，区间每次缩 ⅓。求谷值方向相反。

AC代码

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

int n;
vector<double> coef;                           // 从高次到低次的系数

// 秦九韶格式求 f(x)
double f(double x) {
    double r = 0;
    for (double c : coef) r = r * x + c;
    return r;
}

int main() {
    double l, r;
    cin >> n >> l >> r;
    coef.resize(n + 1);
    for (auto& c : coef) cin >> c;
    // 三分求单峰函数峰值点：两个三分点向中间收缩
    while (r - l > 1e-6) {
        double m1 = l + (r - l) / 3;
        double m2 = r - (r - l) / 3;
        if (f(m1) < f(m2)) l = m1;             // 峰在 [m1, r]
        else r = m2;                           // 峰在 [l, m2]
    }
    printf("%.5f\n", l);
    return 0;
}

函数19

函数

题目描述

给定 \(n\) 个二次函数 \(f_i(x) = a_i x^2 + b_i x + c_i\)，设 \(F(x) = \max\{f_1(x), \ldots, f_n(x)\}\)，求 \(F(x)\) 在 \([0, 1000]\) 上的最小值（保留 4 位小数）。二次函数可能退化成一次。

输入格式

第一行一个正整数 \(T\)，表示数据组数。每组数据：第一行一个正整数 \(n\)；接下来 \(n\) 行每行三个整数 \(a, b, c\)。

输出格式

每组数据一行，为 \(F(x)\) 的最小值（保留 4 位小数）。

样例输入

1
2
3
4
1
2
1 -4 5
1 -4 6

样例输出

1
2.0000

数据范围

  • \(T \le 10\)，\(n \le 10^4\)，\(0 \le a \le 100\)，\(|b|, |c| \le 5 \times 10^3\)
函数 AC 代码

解题思路

\(\max\) of 二次函数是下凸函数（开口向上的函数取 max 仍是下凸）→ 三分求最小值，与求最大方向相反：\(F(m_1) < F(m_2)\) 时最小值在左半。多组数据每次重读重算。

AC代码

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

int n;
vector<double> A, B, C;

// F(x) = max{a x^2 + b x + c}，下凸函数 → 三分求最小值
double F(double x) {
    double r = -1e18;
    for (int i = 0; i < n; i++)
        r = max(r, A[i] * x * x + B[i] * x + C[i]);
    return r;
}

int main() {
    int T;
    cin >> T;
    while (T--) {
        cin >> n;
        A.resize(n);
        B.resize(n);
        C.resize(n);
        for (int i = 0; i < n; i++) cin >> A[i] >> B[i] >> C[i];
        double l = 0, r = 1000;
        while (r - l > 1e-7) {
            double m1 = l + (r - l) / 3;
            double m2 = r - (r - l) / 3;
            if (F(m1) < F(m2)) r = m2;         // 最小值在 [l, m2]
            else l = m1;                       // 最小值在 [m1, r]
        }
        printf("%.4f\n", F(l));
    }
    return 0;
}

单峰函数求最值20

单峰函数求最值

题目描述

给定二次函数 \(y = ax^2 + bx + c\)（\(a < 0\)，开口向下）与区间 \([l, r]\)，其顶点（峰值点）保证在区间内。用三分法求峰值点的横坐标，保留 6 位小数。

输入格式

第一行三个实数 \(a, b, c\)（\(a < 0\)）；第二行两个实数 \(l, r\)。

输出格式

峰值点的横坐标，保留 6 位小数。

样例输入

1
2
-1 6 1
0 10

样例输出

1
3.000000

（顶点横坐标 \(x = -b / 2a = 3\)。）

数据范围

  • \(-100 \le a < 0\)，\(|b|, |c| \le 100\)，顶点横坐标在 \([l, r]\) 内

⬇ 点击下载数据包

单峰函数求最值 AC 代码

解题思路

三分模板的直接应用：\(m_1, m_2\) 两点函数值比较，峰在值大的一侧。可用闭式 \(x = -b / (2a)\) 对账验证三分结果。

AC代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
#include <bits/stdc++.h>
using namespace std;

double a, b, c, l, r;

// y = a x^2 + b x + c（a < 0，开口向下）
double y(double x) { return a * x * x + b * x + c; }

int main() {
    cin >> a >> b >> c >> l >> r;
    // 三分求单峰函数的峰值点
    while (r - l > 1e-7) {
        double m1 = l + (r - l) / 3;
        double m2 = r - (r - l) / 3;
        if (y(m1) < y(m2)) l = m1;             // 峰在 [m1, r]
        else r = m2;                           // 峰在 [l, m2]
    }
    printf("%.6f\n", l);
    return 0;
}

山峰数组21

山峰数组

题目描述

长度为 \(n\) 的山脉数组：存在一个峰顶下标 \(p\)（\(2 \le p \le n-1\)），使得 \(a_1 < a_2 < \cdots < a_p\) 且 \(a_p > a_{p+1} > \cdots > a_n\)（先严格递增、后严格递减）。求峰顶下标 \(p\)。

输入格式

第一行一个整数 \(n\)；第二行 \(n\) 个整数，为山脉数组。

输出格式

一个整数，为峰顶下标。

样例输入

1
2
8
1 3 5 9 12 8 6 4

样例输出

1
5

数据范围

  • \(3 \le n \le 10^5\)
  • \(1 \le a_i \le 10^9\)

⬇ 点击下载数据包

山峰数组 AC 代码

解题思路

三分的对象不一定是一个数学式子，数组下标也可以三分：\(a_i\) 关于下标 \(i\) 先增后减，是天然的单峰「函数」。这是整数三分——把 \(r-l\) 缩到 \(\le 2\) 后，剩余的小区间要暴力扫一遍收尾，避免整数取整漏掉峰顶。

AC代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
#include <bits/stdc++.h>
using namespace std;

int n;
long long a[100005];

int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i];
    int l = 1, r = n;
    while (r - l > 2) {                         // 整数三分：区间缩到 ≤3 再暴力收尾
        int m1 = l + (r - l) / 3, m2 = r - (r - l) / 3;
        if (a[m1] < a[m2]) l = m1 + 1;          // 峰必在 m1 右侧
        else r = m2 - 1;                        // a[m1] ≥ a[m2] 时峰不在 m2 右侧
    }
    int p = l;                                  // 小区间暴力找最大（整数三分收尾）
    for (int i = l + 1; i <= r; i++)
        if (a[i] > a[p]) p = i;
    cout << p << "\n";
    return 0;
}

山谷数组22

山谷数组

题目描述

长度为 \(n\) 的山谷数组：存在一个谷底下标 \(v\)（\(2 \le v \le n-1\)），使得 \(a_1 > a_2 > \cdots > a_v\) 且 \(a_v < a_{v+1} < \cdots < a_n\)（先严格递减、后严格递增）。求谷底下标 \(v\)。

输入格式

第一行一个整数 \(n\)；第二行 \(n\) 个整数，为山谷数组。

输出格式

一个整数，为谷底下标。

样例输入

1
2
8
20 14 9 5 2 3 7 16

样例输出

1
5

数据范围

  • \(3 \le n \le 10^5\)
  • \(1 \le a_i \le 10^9\)

⬇ 点击下载数据包

山谷数组 AC 代码

解题思路

与「山峰数组」成对：三分同样能求单谷函数的最小值——只需把比较方向反过来（\(a_{m_1} > a_{m_2}\) 时舍去左侧）。收尾同样用小区间暴力找最小。

AC代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
#include <bits/stdc++.h>
using namespace std;

int n;
long long a[100005];

int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i];
    int l = 1, r = n;
    while (r - l > 2) {                         // 整数三分：区间缩到 ≤3 再暴力收尾
        int m1 = l + (r - l) / 3, m2 = r - (r - l) / 3;
        if (a[m1] > a[m2]) l = m1 + 1;          // 谷必在 m1 右侧（与山峰题比较方向相反）
        else r = m2 - 1;
    }
    int p = l;                                  // 小区间暴力找最小
    for (int i = l + 1; i <= r; i++)
        if (a[i] < a[p]) p = i;
    cout << p << "\n";
    return 0;
}

  1. 二分查找模板 · 经典模板题（自拟）。 ↩

  2. 二分左边界模板 · 经典模板题（自拟）。 ↩

  3. 二分右边界模板 · 经典模板题（自拟）。 ↩

  4. 左右边界组合 · 经典模板题（自拟）。 ↩

  5. 答案记录式查找 · 经典模板题（自拟）。 ↩

  6. 值域二分 · 经典模板题（自拟）。 ↩

  7. 实数二分（两种收敛写法） · 经典模板题（自拟）。 ↩

  8. 实数二分求根 · 洛谷 P1024 · NOIP2001。 ↩

  9. 实数二分答案 · 洛谷 P1163。 ↩

  10. 二分答案 · 最大化最小值 · 洛谷 P2440。 ↩

  11. 二分答案 · 方向辨析 · 洛谷 P1873 · COCI。 ↩

  12. 二分答案 · 最小值最大化 · 洛谷 P2678 · NOIP2015。 ↩

  13. 二分答案 + 贪心判定 · 洛谷 P1824 · USACO。 ↩

  14. 二分答案 · 最小化最大值 · 洛谷 P1182。 ↩

  15. 二分答案 · 镜像题 · 洛谷 P3853 · TJOI2007。 ↩

  16. 旋转数组二分 · 经典模板题（自拟）。 ↩

  17. 降序数组二分 · 经典入门题（自拟）。 ↩

  18. 三分求峰 · 洛谷 P3382。 ↩

  19. 三分求谷 · 洛谷 P1883 · ICPC。 ↩

  20. 三分求二次函数峰 · 经典模板题（自拟）。 ↩

  21. 整数三分·单峰 · 经典模板题（自拟）。 ↩

  22. 整数三分·单谷 · 经典模板题（自拟）。 ↩

  23. 实数二分（含负数） · 经典模板题（自拟）。 ↩

  24. 单调实数二分求零点 · 经典模板题（自拟）。 ↩

  25. 二分答案 · 最小化最大极差 · 经典模板题（自拟）。 ↩

  26. 二分答案 · 最小化最大时间 · 经典贪心判定题（自拟）。 ↩

  27. 旋转数组查找目标 · 经典模板题（自拟）。 ↩

  28. 左右边界组合 · 经典模板题（自拟）。 ↩

  29. 归并扫描第 k 小 · 经典模板题（自拟）。 ↩

  30. 有序矩阵查找 · 经典模板题（自拟）。 ↩