大家还知道怎么在一本很厚的词典查找一个单词吗？字典中的单词是按照“字典序”进行排序的，比如 code<pan<pancake 。如果我们要找一个单词，就要将字典从中间翻开，然后将这面单词跟想要找的单词比较。如果这面单词在需要寻找的单词之前，就将字典往后翻，否则就往前翻，直到找到准确的单词为止。 大家可以发现，越接近需要查询的单词，翻动书面的页数就越少。你肯定不会从第一页开始一面一面翻，逐个查看每个单词是否就是自己想要查的单词，这样做就太慢了。虽然实际情况不是那么精确，但是基本上使用了“二分思想”。 如果序列是有序的，就可以通过二分查找快速定位所需要的数据。除此之外，二分思想还能求出可行解的最值问题，比如想知道某款手机最高能多少楼高度摔下来而不会摔坏，使用二分的方式可以用最小实验次数就能得到结果（当然你需要准备好几个样品）。

一、二分查找

13.1 查找

题目描述

输入 \(n\) 个不超过 \(10^9\) 的单调不减的（就是后面的数字不小于前面的数字）非负整数 \(a_1,a_2,\dots,a_{n}\)，然后进行 \(m\) 次询问。对于每次询问，给出一个整数 \(q\)，要求输出这个数字在序列中第一次出现的编号，如果没有找到的话输出 \(-1\) 。

输入格式

第一行 \(2\) 个整数 \(n\) 和 \(m\)，表示数字个数和询问次数。 第二行 \(n\) 个整数，表示这些待查询的数字。 第三行 \(m\) 个整数，表示询问这些数字的编号，从 \(1\) 开始编号。

输出格式

输出一行，\(m\) 个整数，以空格隔开，表示答案。

样例 #1

样例输入 #1

11 3
1 3 3 3 5 7 9 11 13 15 15
1 3 6

样例输出 #1

1 2 -1

提示

数据保证，\(1 \leq n \leq 10^6\)，\(0 \leq a_i,q \leq 10^9\)，\(1 \leq m \leq 10^5\) 本题输入输出量较大，请使用较快的 IO 方式。

#include<iostream>
#define MAXN 1000010
using namespace std;
int a[MAXN], m, n, q;
int find(int x) {
    int l = 1, r = n+1;
    while (l < r) {
        int mid = l+(r-l)/2;
        if (a[mid] >= x)   r=mid;
        else l = mid + 1;
    }
    if (a[l] == x)  return l;
    else return -1;
}
int main() {
    cin >>n >> m;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    for (int i = 0; i < m; i++) {
        cin >> q;
        cout << find(q) << " ";
    }
    return 0;
}

补充知识：STL中的lower_bound()和upper_bound() 头文件：algorithm

lower_bound(begin,end,val):在值有序的数组连续地址[begin,end)中找到第一个位置并返回其地址，使得val插入在这个前面，整个数组仍然保持有序。 upper_bound(begin,end,val):在值有序的数组连续地址[begin,end)中找到最后一个位置并返回其地址，使得val插入在这个前面，整个数组仍然保持有序。 简易理解：比较 lower_bound() 和 upper_bound() 的区别 lower_bound(value) 返回 第一个不小于 value 的元素（即 value 可能是返回的元素），它允许找到等于 value 的元素。 upper_bound(value) 返回 第一个大于 value 的元素，它不允许找到等于 value 的元素。

13.2 A-B 数对

题目背景

出题是一件痛苦的事情！ 相同的题目看多了也会有审美疲劳，于是我舍弃了大家所熟悉的 A+B Problem，改用 A-B 了哈哈！

题目描述

给出一串正整数数列以及一个正整数 \(C\)，要求计算出所有满足 \(A - B = C\) 的数对的个数（不同位置的数字一样的数对算不同的数对）。

输入格式

输入共两行。 第一行，两个正整数 \(N,C\)。 第二行，\(N\) 个正整数，作为要求处理的那串数。

输出格式

一行，表示该串正整数中包含的满足 \(A - B = C\) 的数对的个数。

样例 #1

样例输入 #1

4 1
1 1 2 3

样例输出 #1

3

提示

对于 \(75\%\) 的数据，\(1 \leq N \leq 2000\)。 对于 \(100\%\) 的数据，\(1 \leq N \leq 2 \times 10^5\)，\(0 \leq a_i <2^{30}\)，\(1 \leq C < 2^{30}\)。

法一、O(n log n)

#include<cstdio>
#include<algorithm>
#define maxn 200010
using namespace std;
typedef long long LL;
LL a[maxn];
int n, c;
int main() {
    scanf("%d%d", &n, &c);
    for (int i = 0; i < n; i++) {
        scanf("%lld", &a[i]);
    }
    sort(a, a + n);
    LL tot = 0;
    for (int i = 0; i < n; i++) {
        tot += upper_bound(a, a + n, a[i] + c) - lower_bound(a, a + n, a[i] + c);
    }
    printf("%lld", tot);
}

解释：

给定条件是我们需要计算所有满足 A - B = C 的数对 (A, B)。根据这个条件，可以将问题转化为： - 对于每个元素 A = a[i]，我们需要查找 B = a[j]，使得 a[i] - a[j] = C，即 a[j] = a[i] - C。 因此，我们的目标是在数组中找出所有满足 a[j] = a[i] - C 的元素。

使用 lower_bound 和 upper_bound

1. lower_bound 和 upper_bound 定义：
2. lower_bound(a, a + n, x) 返回的是第一个大于等于 x 的元素的位置。
3. upper_bound(a, a + n, x) 返回的是第一个大于 x 的元素的位置。
4. 对于每个 a[i]，我们需要寻找 a[j] = a[i] - c 的位置。为了查找这个值在数组中的出现位置，我们可以使用 lower_bound 和 upper_bound 来查找这个值的区间。

upper_bound 和 lower_bound 的差值

假设我们要找的值是 a[i] - c（即 B = a[i] - C）： - lower_bound(a, a + n, a[i] - c) 返回的是数组中第一个大于等于 a[i] - c 的位置。 - upper_bound(a, a + n, a[i] - c) 返回的是数组中第一个大于 a[i] - c 的位置。 对于满足 a[j] = a[i] - C 的所有 j，它们的位置就落在 lower_bound 和 upper_bound 之间。因此，upper_bound - lower_bound 的差值给出的是这个值出现的次数。

示例

假设我们有一个数组 a = [1, 1, 2, 3]，并且我们想查找满足 a[i] - a[j] = 1 的数对。 - 设 c = 1，即我们需要找 a[j] = a[i] - 1。 - 对于每个 a[i]，我们会进行以下查询： - 对于 a[0] = 1，我们需要查找 a[j] = 0。由于 0 不在数组中，lower_bound(a, a + n, 0) 和 upper_bound(a, a + n, 0) 都会返回指向第一个元素的迭代器，差值为 0。 - 对于 a[1] = 1，同样，a[j] = 0，upper_bound - lower_bound = 0。 - 对于 a[2] = 2，我们需要查找 a[j] = 1，它在数组中的位置是两个 1，所以 upper_bound - lower_bound = 2。 - 对于 a[3] = 3，我们需要查找 a[j] = 2，它在数组中的位置是 2，所以 upper_bound - lower_bound = 1。

修正代码的部分：

LL tot = 0;
for (int i = 0; i < n; i++) {
    tot += upper_bound(a, a + n, a[i] - c) - lower_bound(a, a + n, a[i] - c);
}

- 对于每个 a[i]，upper_bound(a, a + n, a[i] - c) 查找 a[j] = a[i] - c 在数组中的第一个大于该值的位置。 - lower_bound(a, a + n, a[i] - c) 查找第一个大于等于 a[i] - c 的位置。 这两个值的差值即为 a[i] - c 这个值在数组中出现的次数。

时间复杂度

• lower_bound 和 upper_bound 都是二分查找，时间复杂度是 O(log n)。
• 所以对于每个元素 a[i]，我们进行一次 upper_bound 和一次 lower_bound，总的时间复杂度是 O(n log n)。

总结

• upper_bound 和 lower_bound 用于查找指定元素的位置区间，通过这两个函数的差值可以高效地计算满足条件的数对个数。
• 时间复杂度为 O(n log n)，非常适合处理大数据量的情况。

法二、O(n)

#include<cstdio>
#include<algorithm>
#define maxn 200010
using namespace std;
typedef long long LL;
LL a[maxn];
int n, c;
int main() {
    scanf("%d%d", &n, &c);
    for (int i = 0; i < n; i++) {
        scanf("%lld", &a[i]);
    }
    sort(a, a + n);
    LL tot = 0;
    for (int i = 0, L = 0, R = 0; i < n; i++) {
        while (L < n && a[L] < a[i] + c) {
            L++;
        }
        while (R < n && a[R] <= a[i] + c) {
            R++;
        }
        tot += R - L;
    }
    printf("%lld", tot);
}

二、二分答案

13.3 EKO / 砍树

题目描述

伐木工人 Mirko 需要砍 \(M\) 米长的木材。对 Mirko 来说这是很简单的工作，因为他有一个漂亮的新伐木机，可以如野火一般砍伐森林。不过，Mirko 只被允许砍伐一排树。 Mirko 的伐木机工作流程如下：Mirko 设置一个高度参数 \(H\)（米），伐木机升起一个巨大的锯片到高度 \(H\)，并锯掉所有树比 \(H\) 高的部分（当然，树木不高于 \(H\) 米的部分保持不变）。Mirko 就得到树木被锯下的部分。例如，如果一排树的高度分别为 \(20,15,10\) 和 \(17\)，Mirko 把锯片升到 \(15\) 米的高度，切割后树木剩下的高度将是 \(15,15,10\) 和 \(15\)，而 Mirko 将从第 \(1\) 棵树得到 \(5\) 米，从第 \(4\) 棵树得到 \(2\) 米，共得到 \(7\) 米木材。 Mirko 非常关注生态保护，所以他不会砍掉过多的木材。这也是他尽可能高地设定伐木机锯片的原因。请帮助 Mirko 找到伐木机锯片的最大的整数高度 \(H\)，使得他能得到的木材至少为 \(M\) 米。换句话说，如果再升高 \(1\) 米，他将得不到 \(M\) 米木材。

输入格式

第 \(1\) 行 \(2\) 个整数 \(N\) 和 \(M\)，\(N\) 表示树木的数量，\(M\) 表示需要的木材总长度。 第 \(2\) 行 \(N\) 个整数表示每棵树的高度。

输出格式

\(1\) 个整数，表示锯片的最高高度。

样例 #1

样例输入 #1

4 7
20 15 10 17

样例输出 #1

15

样例 #2

样例输入 #2

5 20
4 42 40 26 46

样例输出 #2

36

提示

对于 \(100\%\) 的测试数据，\(1\le N\le10^6\)，\(1\le M\le2\times10^9\)，树的高度 \(\le 4\times 10^5\)，所有树的高度总和 \(>M\)。

#include<cstdio>
using namespace std;
#define maxn 1000010
typedef long long LL;
LL a[maxn], n, m;
bool P(int h) {
    LL tot = 0;
    for (int i = 1; i <= n; i++) {
        if (a[i] > h)  tot += a[i] - h;
    }
    return tot >= m;
}

int main() {
    scanf("%lld%lld", &n, &m);
    for (int i = 1; i <= n; i++) {
        scanf("%lld", &a[i]);
    }
    int L = 0, R = 1e9, ans, mid;
    while (L <= R) {
        if (P(mid = L + R >> 1))
            ans = mid, L = mid + 1;
        else
            R = mid - 1;
    }
    printf("%d", ans);
}

13.4 进击的奶牛

题目描述

Farmer John 建造了一个有 \(N\)（\(2 \leq N \leq 10 ^ 5\)) 个隔间的牛棚，这些隔间分布在一条直线上，坐标是 \(x _ 1, x _ 2, \cdots, x _ N\)（\(0 \leq x _ i \leq 10 ^ 9\)）。 他的 \(C\)（\(2 \leq C \leq N\)）头牛不满于隔间的位置分布，它们为牛棚里其他的牛的存在而愤怒。为了防止牛之间的互相打斗，Farmer John 想把这些牛安置在指定的隔间，所有牛中相邻两头的最近距离越大越好。那么，这个最大的最近距离是多少呢？

输入格式

第 \(1\) 行：两个用空格隔开的数字 \(N\) 和 \(C\)。 第 \(2 \sim N+1\) 行：每行一个整数，表示每个隔间的坐标。

输出格式

输出只有一行，即相邻两头牛最大的最近距离。

样例 #1

样例输入 #1

5 3
1
2
8
4
9

样例输出 #1

3

标答

#include<cstdio>
#include<algorithm>
using namespace std;
#define maxn 1000010
#define INF 1e9
int a[maxn], n, c;
bool P(int d) {
    int k = 0, last = -INF;
    for (int i = 1; i <= n; i++) {
        if (a[i] - last >= d)
            last = a[i], k++;
    }
    return k >= c;
}

int main() {
    scanf("%d%d", &n, &c);
    for (int i = 1; i <= n; i++)
        scanf("%d", &a[i]);
    sort(a + 1, a + 1 + n);
    int L = 0, R = INF, ans, mid;
    while (L <= R) {
        if (P(mid = L + R >> 1))
            ans = mid, L = mid + 1;
        else
            R = mid - 1;
    }
    printf("%d", ans);
}

较好的理解方式

#include <cstdio>
#include <algorithm>
using namespace std;
#define maxn 1000010
int a[maxn], n, c;

// 判断是否可以用最小距离d放置所有的牛
bool P(int d) {
    int k = 1, last = a[1];  // 放置第一头牛在最左边
    for (int i = 2; i <= n; i++) {
        if (a[i] - last >= d) {  // 如果当前隔间与上一个放置的牛的距离大于等于d
            last = a[i];  // 放置这头牛
            k++;  // 牛的数量增加
            if (k == c) return true;  // 如果所有牛都被放置成功
        }
    }
    return false;  // 如果不能放置所有的牛
}

int main() {
    // 读取输入
    scanf("%d%d", &n, &c);
    for (int i = 1; i <= n; i++) {
        scanf("%d", &a[i]);
    }

    // 排序隔间的位置
    sort(a + 1, a + 1 + n);

    // 二分查找最大最小距离
    int L = 0, R = a[n] - a[1], ans;
    while (L <= R) {
        int mid = (L + R) >> 1;  // 中间值
        if (P(mid)) {  // 如果可以放置所有牛
            ans = mid;  // 更新答案
            L = mid + 1;  // 尝试更大的最小距离
        } else {
            R = mid - 1;  // 尝试更小的最小距离
        }
    }

    // 输出结果
    printf("%d\n", ans);
}

解释：从头清晰地解释整个过程，特别是关于 判断函数 P(d) 的执行逻辑。（以样例为例）

---

题目简述

我们需要在牛棚的位置 a = [1, 2, 8, 4, 9] 中放置 3 头牛（C = 3），让所有相邻两头牛的最小距离尽可能大。

二分查找的核心

• 最小距离 d 的范围：从 L = 0 到 R = 最大坐标差 = 9 - 1 = 8。
• 我们通过 二分查找找到最大的可行距离 d。

---

判断函数 P(d)

函数 P(d) 检查是否可以在所有牛棚中，以最小间距 d 成功放置 C 头牛。 - 输入： 一个最小距离 d。 - 输出： true（可以放置）或 false（无法放置）。 - 逻辑： 1. 按顺序检查牛棚位置，放置第 1 头牛。 2. 从当前位置往后，找到满足距离 >= d 的位置放置下一头牛，直到放置完所有 C 头牛。 3. 如果成功放置 C 头牛，返回 true；否则返回 false。

---

完整过程

输入数据

N = 5, C = 3
牛棚位置：a = [1, 2, 8, 4, 9]

排序

先对位置排序：

a = [1, 2, 4, 8, 9]

初始化二分范围

• L = 0（最小可能距离）。
• R = 8（最大可能距离）。
• ans = 0（记录答案）。

---

二分查找过程

第一次迭代

• 计算中间值：mid = (L + R) >> 1 = (0 + 8) >> 1 = 4。
• 检查 P(4)：
• 放置第 1 头牛在位置 a[0] = 1。
  • 当前最后一头牛的位置：last = 1。
• 寻找放置第 2 头牛的位置：
  • 从 a[1] = 2 开始：
  • 2 - 1 = 1，不满足。
  • 4 - 1 = 3，不满足。
  • 8 - 1 = 7，满足，放置在 a[3] = 8。
  • 当前最后一头牛的位置：last = 8。
• 寻找放置第 3 头牛的位置：
  • 从 a[4] = 9 开始：
  • 9 - 8 = 1，不满足。
  • 无法放置第 3 头牛。
• 结果： P(4) = false。
• 更新搜索范围：R = mid - 1 = 3。

---

第二次迭代

• 计算中间值：mid = (L + R) >> 1 = (0 + 3) >> 1 = 1。
• 检查 P(1)：
• 放置第 1 头牛在位置 a[0] = 1。
  • 当前最后一头牛的位置：last = 1。
• 寻找放置第 2 头牛的位置：
  • 从 a[1] = 2 开始：
  • 2 - 1 = 1，满足，放置在 a[1] = 2。
  • 当前最后一头牛的位置：last = 2。
• 寻找放置第 3 头牛的位置：
  • 从 a[2] = 4 开始：
  • 4 - 2 = 2，满足，放置在 a[2] = 4。
  • 成功放置 3 头牛。
• 结果： P(1) = true。
• 更新搜索范围：L = mid + 1 = 2，并记录答案：ans = 1。

---

第三次迭代

• 计算中间值：mid = (L + R) >> 1 = (2 + 3) >> 1 = 2。
• 检查 P(2)：
• 放置第 1 头牛在位置 a[0] = 1。
  • 当前最后一头牛的位置：last = 1。
• 寻找放置第 2 头牛的位置：
  • 从 a[1] = 2 开始：
  • 2 - 1 = 1，不满足。
  • 4 - 1 = 3，满足，放置在 a[2] = 4。
  • 当前最后一头牛的位置：last = 4。
• 寻找放置第 3 头牛的位置：
  • 从 a[3] = 8 开始：
  • 8 - 4 = 4，满足，放置在 a[3] = 8。
  • 成功放置 3 头牛。
• 结果： P(2) = true。
• 更新搜索范围：L = mid + 1 = 3，并记录答案：ans = 2。

---

第四次迭代

• 计算中间值：mid = (L + R) >> 1 = (3 + 3) >> 1 = 3。
• 检查 P(3)：
• 放置第 1 头牛在位置 a[0] = 1。
  • 当前最后一头牛的位置：last = 1。
• 寻找放置第 2 头牛的位置：
  • 从 a[1] = 2 开始：
  • 2 - 1 = 1，不满足。
  • 4 - 1 = 3，满足，放置在 a[2] = 4。
  • 当前最后一头牛的位置：last = 4。
• 寻找放置第 3 头牛的位置：
  • 从 a[3] = 8 开始：
  • 8 - 4 = 4，满足，放置在 a[3] = 8。
  • 成功放置 3 头牛。
• 结果： P(3) = true。
• 更新搜索范围：L = mid + 1 = 4，并记录答案：ans = 3。

---

二分查找结束

• 当 L > R 时，二分查找结束。
• 最终答案：ans = 3。

---

总结

在距离为 3 时： - 放置第 1 头牛在位置 1。 - 放置第 2 头牛在位置 4。 - 放置第 3 头牛在位置 8。 成功满足条件，因此输出：

3

13.5 一元三次方程求解

题目描述

有形如：\(a x^3 + b x^2 + c x + d = 0\) 这样的一个一元三次方程。给出该方程中各项的系数（\(a,b,c,d\) 均为实数），并约定该方程存在三个不同实根（根的范围在 \(-100\) 至 \(100\) 之间），且根与根之差的绝对值 \(\ge 1\)。要求由小到大依次在同一行输出这三个实根(根与根之间留有空格)，并精确到小数点后 \(2\) 位。 提示：记方程 \(f(x) = 0\)，若存在 \(2\) 个数 \(x_1\) 和 \(x_2\)，且 \(x_1 < x_2\)，\(f(x_1) \times f(x_2) < 0\)，则在 \((x_1, x_2)\) 之间一定有一个根。

输入格式

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

输出格式

一行，\(3\) 个实根，从小到大输出，并精确到小数点后 \(2\) 位。

样例 #1

样例输入 #1

1 -5 -4 20

样例输出 #1

-2.00 2.00 5.00

零点存在性定理

定理内容

零点存在性定理（也称为 介值定理 或 中值定理）说明了对于连续函数，在给定区间内，如果函数值在区间的两端符号不同，那么函数一定在该区间内有至少一个零点。

定理表述

设函数 \( f \) 在区间 \([a, b]\) 上是连续的，如果：

\[ f(a) \cdot f(b) < 0 \]

那么，存在至少一个点 \( c \in (a, b) \)，使得：

\[ f(c) = 0 \]

几何解释

若函数在区间 \([a, b]\) 的两端 \(a\) 和 \(b\) 处的值符号不同（即一个为正，一个为负），且该函数是连续的，那么必定有一个点 \(c\)，使得函数值为零（即函数图像一定穿过 \(x\)-轴）。

#include<cstdio>
#include<iostream>
#include<cmath>
using namespace std;
#define eps 1e-4
double A, B, C, D;
double f(double x) {
    return A * x * x * x + B * x * x + C * x + D;
}
int main() {
    cin >> A >> B >> C >> D;
    for (int i = -100; i <= 100; i++) {
        double L = i, R = i + 1, mid;
        if (fabs(f(L)) < eps)
            printf("%.2lf ", L);
        else if (fabs(f(R)) < eps)
            continue;
        else if (f(L) * f(R) < 0) {
            while (R - L > eps) {
                mid = (L + R) / 2;
                if (f(mid) * f(R) > 0)
                    R = mid;
                else
                    L = mid;
            }
            printf("%.2lf ", L);
        }
    }
}

END