Day 22 · 二分查找：在有序里快速定位

题意：给 n 个单调不减的非负整数，m 次询问，每次给一个 q，输出 q 在序列中第一次出现的位置（从 1 开始编号），没出现就输出 −1。

思路

数组已经单调不减，直接就是手写二分（写法一：闭区间 + ans）的模板题。

要的是「第一个 ≥ q 的位置」，所以命中之后不能停，要记下答案再往左找。

复杂度：排序都不用做（输入已经有序），每次询问 O(log n) → 总 O(m log n) ≈ 10⁵ × 20 = 2×10⁶。

样例数组的定位过程：

（上面用的是 1 开始的编号）查 3 → 第一个 3 在第 2 位；查 6 → 第一个 ≥ 6 的数在第 6 位，但它是 7 不是 6 → 输出 −1。

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

1 2 -1

完整代码

#include <cstdio>
using namespace std;

int a[1000005];
int n, m;

int main(){
    scanf("%d %d", &n, &m);
    for(int i = 0; i < n; i++) scanf("%d", &a[i]);

    for(int k = 0; k < m; k++){
        int q;
        scanf("%d", &q);
        // ★ 手写 lower_bound：找第一个 >= q 的位置
        int l = 0, r = n - 1, ans = -1;
        while(l <= r){
            int mid = l + (r - l) / 2;      // 防溢出写法
            if(a[mid] >= q){
                ans = mid;                  // 先记下来，再往左边继续找
                r = mid - 1;
            } else {
                l = mid + 1;
            }
        }
        if(k) printf(" ");
        // ans 是第一个 >= q 的位置（没有就是 -1），还要确认它真的等于 q
        if(ans == -1 || a[ans] != q) printf("-1");
        else printf("%d", ans + 1);         // 题目要求输出 1 开始的编号
    }
    printf("\n");
    return 0;
}

易错点

• 命中后直接 return：那样找到的是「某一个」q，不是「第一个」。必须 ans = mid; r = mid - 1; 继续往左。
• 不验证 a[ans] == q：q = 6 时二分返回的是 7 的位置，不验证就会输出错误的位置而不是 −1。
• 忘记 +1：题目编号从 1 开始，ans 是数组下标，要输出 ans + 1。
• 用 cin 不开同步：10⁶ 个数 + 10⁵ 次询问，cin 不带 ios::sync_with_stdio(false) 会很慢。
• 输出格式：m 个答案在同一行用空格隔开。用「第一个不加空格、后面都加」的写法（if(k) printf(" ");）最省事，也不用担心行尾多一个空格。
• 数组下标从 0 开始，所以 a[1000005] 够用（n 最大 10⁶，多开 5 个保险）。

题意：给一串正整数和一个正整数 C，数出有多少个数对满足 A − B = C。不同位置的相同数字算不同的数对。

思路

等式 A − B = C 等价于 A = B + C，或者说「对每个 A，找有多少个 B 等于 A − C」。

于是：

1. 排序（二分的必要前提）。
2. 遍历每个 a[i] 当作 A，目标是 B = a[i] − C。
   代码里写的是 target = a[i] + C，因为「数组里有多少个 a[j] = a[i] + C」和「有多少个数对差为 C」是一一对应的，两种写法都对，只是把谁当 A 的区别。
3. 用 upper_bound − lower_bound 数出 target 出现了几次，累加进答案。

复杂度：O(N log N)。

4 1
1 1 2 3

3

C = 1，排序后还是 1 1 2 3。
A = 1（第一个）：B = A + 1 = 2，数组里有 1 个 → +1
A = 1（第二个）：同上 → +1
A = 2：B = 3，数组里有 1 个 → +1
A = 3：B = 4，没有 → +0
共 3。

完整代码

#include <iostream>
#include <algorithm>
using namespace std;

int a[200005];

int main(){
    ios::sync_with_stdio(false);            // 关掉 cin/cout 与 C 输入输出的同步，提速
    cin.tie(0);

    int n;
    long long c;
    cin >> n >> c;
    for(int i = 0; i < n; i++) cin >> a[i];
    sort(a, a + n);                         // ★ 二分的前提：先排序

    long long ans = 0;                      // ★ 答案要用 long long
    for(int i = 0; i < n; i++){
        long long target = (long long)a[i] + c;     // 需要多少个 a[j] == a[i] + c
        // 数 target 出现了几次：upper_bound - lower_bound
        int lo = (int)(lower_bound(a, a + n, target) - a);
        int hi = (int)(upper_bound(a, a + n, target) - a);
        ans += hi - lo;
    }
    cout << ans << endl;
    return 0;
}

易错点

• 答案用 int：会溢出 → WA。这是本题的头号错误。
• 忘记排序：二分在乱序数组上毫无意义。
• 把重复元素只算一次：题目明确「不同位置的数字一样的数对算不同的数对」，所以两个 1 要分别算，用 ub − lb 正好自动处理。
• target 用 int 相加：aᵢ 可以接近 2³⁰，a[i] + C 会超过 int 上限（2³¹−1）吗？本题不会（2³⁰−1 + 2³⁰−1 = 2³¹−2 < 2³¹−1），但写成 (long long)a[i] + c 更稳，不用去算边界。
• 把 lower_bound 传成 a + n - 1：范围写错会漏掉最后一个元素。标准的写法是 [a, a+n)。
• C 的读入格式写错：C 可以到 2³⁰ 量级，用 scanf("%d", &c) 读成 int 在本题还能勉强撑住，但换成更大的数据就会读错。答案和 C 一律用 long long，读入也用 cin >> c 或 %lld。
• 用 cin 却不开同步：读 2×10⁵ 个数会慢一截，记得 ios::sync_with_stdio(false); cin.tie(0);。

题意：m 所学校的分数线 aᵢ，n 个学生的估分 bᵢ。给每个学生配一所学校，使「分数线与估分之差」最小（可以高也可以低），这个最小值叫这名学生的不满意度。求所有学生不满意度的总和。

思路

先给分数线排序。对每个学生的估分 b：

1. 用 lower_bound 找到第一个 ≥ b 的分数线，位置记为 p。
2. 离 b 最近的分数线，一定是 a[p] 和 a[p−1] 中的一个（见下面的解释），把两者的差值取小的那个即可。
3. 注意边界：p == m 说明所有分数线都 < b，右边没有候选；p == 0 说明所有分数线都 ≥ b，左边没有候选。

4 3
513 598 567 689
500 600 550

32

分数线排序后：513、567、598、689。
估分 500 → 最近的 513，差 13；
估分 600 → 最近的 598，差 2；
估分 550 → 513 差 37，567 差 17，取 17。
合计 13 + 2 + 17 = 32。

完整代码

#include <iostream>
#include <algorithm>
using namespace std;

int a[100005], b[100005];

int main(){
    ios::sync_with_stdio(false);        // 关掉 cin/cout 与 C 输入输出的同步，提速
    cin.tie(0);

    int m, n;
    cin >> m >> n;
    for(int i = 0; i < m; i++) cin >> a[i];
    for(int i = 0; i < n; i++) cin >> b[i];
    sort(a, a + m);                         // 学校分数线排序

    long long ans = 0;                      // ★ 最多 1e5 × 1e6 = 1e11，必须 long long
    for(int i = 0; i < n; i++){
        // p = 第一个 >= b[i] 的分数线
        int p = (int)(lower_bound(a, a + m, b[i]) - a);
        int best = 1 << 30;                 // 先设一个大数
        if(p != m) best = min(best, a[p] - b[i]);       // 右边最近的
        if(p != 0) best = min(best, b[i] - a[p - 1]);   // 左边最近的
        ans += best;
    }
    cout << ans << endl;                    // 用 cout 输出 long long，不会有格式符的问题
    return 0;
}

易错点

• 答案用 int：10¹¹ 溢出 → WA。
• 只看 a[p] 不看 a[p-1]：题目说「可高可低」，只往上看会得到偏大的不满意度。
• 越界访问 a[p-1]：当 p == 0 时 a[-1] 是非法访问，必须判掉。
• 忘记 p == m 的判断：此时 a[p] 指向数组外面。
• 用两重循环暴力：O(nm) = 10¹⁰ → TLE。
• 被「估分可能相等」绕晕：当 a[p] == b[i] 时差值是 0，代码自然就取到 0 了，不用特判。

题意：解方程 ax³ + bx² + cx + d = 0，系数是实数。约定方程有三个不同实根，根都在 [−100, 100] 内，且根与根的差 ≥ 1。从小到大输出三个根，精确到小数点后 2 位。

思路

「根与根之差 ≥ 1」意味着任意长度为 1 的区间里最多只有一个根。于是把 [−100, 100] 按 1 切成 200 个小区间，逐个检查：

• 如果左端点 f(i) 就是 0 → i 本身是根，直接记下；
• 否则看 f(i) 和 f(i+1) 是否异号 → 异号就在 (i, i+1) 里做 100 次实数二分；
• 最后单独补查 x = 100。

因为每个小区间最多一个根，去重只要判断「新根和上一个根相差是否小于 0.5」就行。

浮点判零用相对容差：先求出 f 在整数点上的最大绝对值 maxf，再取 tol = maxf × 1e-9 + 1e-9。

1 -5 -4 20

-2.00 2.00 5.00

这个多项式正好能分解：x³ − 5x² − 4x + 20 = (x + 2)(x − 2)(x − 5)，三个根都是整数。

完整代码

#include <cstdio>
#include <cmath>

double a, b, c, d;
double ans[3];
int cnt = 0;

double f(double x){
    return ((a * x + b) * x + c) * x + d;   // 秦九韶算法，少算几次乘法
}

// 记录一个根；根之间至少差 1，所以差距小于 0.5 的算同一个根
void add(double r){
    for(int i = 0; i < cnt; i++)
        if(fabs(ans[i] - r) < 0.5) return;
    if(cnt < 3) ans[cnt++] = r;
}

int main(){
    scanf("%lf %lf %lf %lf", &a, &b, &c, &d);

    // 用一个「相对」容差判断整数点是不是根，避免系数很大时误判
    double maxf = 0;
    for(int i = -100; i <= 100; i++){
        double v = fabs(f((double)i));
        if(v > maxf) maxf = v;
    }
    double tol = maxf * 1e-9 + 1e-9;

    for(int i = -100; i < 100 && cnt < 3; i++){
        double fl = f((double)i), fr = f((double)(i + 1));
        if(fabs(fl) < tol){                 // 情况 1：整数点本身就是根
            add((double)i);
            continue;
        }
        if(fl * fr < 0){                    // 情况 2：两端异号，区间里必有一个根
            double l = i, r = i + 1;
            for(int k = 0; k < 100; k++){   // 固定二分 100 次，精度足够
                double mid = (l + r) / 2;
                if(f(l) * f(mid) <= 0) r = mid;
                else l = mid;
            }
            add((l + r) / 2);
        }
    }
    if(cnt < 3 && fabs(f(100.0)) < tol) add(100.0);      // 别忘了右端点

    for(int i = 0; i < cnt; i++){
        if(i) printf(" ");
        printf("%.2f", ans[i]);
    }
    printf("\n");
    return 0;
}

易错点

• 只判区间异号，不管整数点是根：根恰好在整数点时，f(i) = 0，两端乘积是 0 而不是负数，fl * fr < 0 不成立，根就被漏掉了。
• 忘记 x = 100：扫描区间是 [−100, 100]，循环里只覆盖到 i = 99 的右端 100，最后一个点要单独判。
• 用 while(r - l > eps)：精度耗尽时 mid 可能等于 l 或 r，区间不再缩小 → 死循环。用固定 100 次更稳。
• 忘记去重：根落在整数点上时，可能被相邻两个区间各认领一次，同一个根输出两遍，第三个根就没位置了。
• 用 fabs(f(i)) == 0 精确判零：浮点误差下几乎不会恰好等于 0，要用容差。
• 容差写死成 1e-6：系数很大时 f 的正常值可能有 10¹² 量级，固定的小容差会把非根点误判成根。所以用相对容差。
• 输出格式：同一行、空格分隔、%.2f。用「第一个不加空格」的写法避免行尾多空格。