【GESP】C++四级练习 luogu-P1296 奶牛的耳语

GESP C++ 四级/五级练习题，排序与双指针（滑动窗口/尺取法）及二分查找的经典应用。题目要求在 $10^6$ 规模下统计所有距离不超过 $d$ 的奶牛坐标数对。考察将 $\mathcal{O}(n^2)$ 暴力枚举优化为 $\mathcal{O}(n \log n)$ 算法的能力，以及防范 32 位整型溢出与快速输入输出技巧。难度⭐⭐。洛谷难度等级普及-。

luogu-P1296 奶牛的耳语

题目要求

题目描述

在你的养牛场，所有的奶牛都养在一排呈直线的牛栏中。一共有 $n$ 头奶牛，其中第 $i$ 头牛在直线上所处的位置可以用一个整数坐标 $p_i(0\le p_i \le 10^8)$ 来表示。在无聊的日子里，奶牛们常常在自己的牛栏里与其它奶牛交流一些八卦新闻。每头奶牛发出的声音响度是一样的，而由于声波的能量衰减，某头奶牛发出的声音只能被与它距离不超过 $d(0 \le d \le 10^4)$ 的奶牛所听到，这样这对奶牛就称为可以相互交流的。现在给出所有奶牛的位置和声音所能传播的最远距离 $d$ ，请你编个程序来计算你的养牛场里究竟有多少对可以相互交流的奶牛。

输入格式

第一行包含两个整数 $n,d$。

第二行包含 $n$ 个整数，每个整数都是一个坐标 $p_i$，描述一头奶牛在直线上的位置。

输出格式

一个数，表示养牛场中可以相互交流奶牛的对数。

输入输出样例 #1

输入 #1

5 10
10 12 16 37 40

输出 #1

4

说明/提示

数据规模：

• 对于 $40\%$ 的数据，$1 \leq n \leq 10^3$。
• 对于 $100\%$ 的数据，$1 \leq n \leq 10^6$。
• 坐标范围：$0 \le p_i \le 10^8$。
• 声音距离：$0 \le d \le 10^4$。

题目分析

本题属于一维数轴上的 区间数对统计问题。给定 $n$ 个点的坐标，要求统计满足距离 $|p_i - p_j| \le d$（$i \ne j$）的无序数对对数。

1. 暴力解法与其局限性

最直观的方法是两重循环枚举所有可能的奶牛对 $(i, j)$（$0 \le i < j < n$）：

• 判断坐标之差是否满足 $|p_i - p_j| \le d$；
• 若满足则答案计数加 1。

复杂度与效率评估：

• 枚举数对总次数为 $\dfrac{n(n-1)}{2}$，时间复杂度为 $\mathcal{O}(n^2)$。
• 在 $40\%$ 数据（$n \le 10^3$）下，计算次数约为 $5 \times 10^5$，可以顺利通过。
• 但在 $100\%$ 数据（$n \le 10^6$）下，总计算次数高达 $\approx 5 \times 10^{11}$ 次。计算机 1 秒内通常只能执行约 $10^8$ 次基本运算，暴力解法将严重超时（TLE）。

2. 优化思路：排序 + 双指针（尺取法）

既然数轴上的距离计算只与相对大小有关，我们可以先将所有奶牛的坐标按升序排序。

排序后的单调性特征

假设排序后的坐标数组为 $p[0], p[1], \dots, p[n-1]$，此时满足 $p[0] \le p[1] \le \dots \le p[n-1]$。 对于任意固定的左端点奶牛 $i$，合法的右侧奶牛 $j$（$j > i$）必须满足： $p[j] - p[i] \le d$

由于数组是单调不降的：

1. 随着左指针 $i$ 从左向右移动（$i$ 递增），$p[i]$ 逐渐增大；
2. 满足 $p[j] - p[i] \le d$ 的最大右端点 $j$ 也必定不会向左回退，即右指针 $j$ 具有单调不减的性质！

双指针滑动扫描过程

坐标数组 (升序): [ 10,  12,  16,  37,  40 ]   (d = 10)
                 ▲        ▲
                 │        │
               i = 0    j = 2   (p[2]-p[0]=6 <= 10, p[3]-p[0]=27 > 10)
               以 i=0 为起点的合法对数: j - i = 2 - 0 = 2 (配对: 12, 16)
               -------------------------------------------------------
                 [ 10,  12,  16,  37,  40 ]
                        ▲     ▲
                        │     │
                      i = 1  j = 2   (p[2]-p[1]=4 <= 10)
                      以 i=1 为起点的合法对数: j - i = 2 - 1 = 1 (配对: 16)
               -------------------------------------------------------
                 [ 10,  12,  16,  37,  40 ]
                              ▲
                              │ (i=2, j=2)
                      以 i=2 为起点的合法对数: j - i = 2 - 2 = 0
               -------------------------------------------------------
                 [ 10,  12,  16,  37,  40 ]
                                  ▲    ▲
                                  │    │
                                i = 3  j = 4 (p[4]-p[3]=3 <= 10)
                      以 i=3 为起点的合法对数: j - i = 4 - 3 = 1 (配对: 40)
               -------------------------------------------------------
总合法对数 = 2 + 1 + 0 + 1 = 4

• 维护右指针 $j$：当 $j + 1 < n$ 且 $p[j + 1] - p[i] \le d$ 时，不断执行 ++j；
• 此时下标在 $[i + 1, j]$ 范围内的所有奶牛均与奶牛 $i$ 可以相互听到，数量为 $j - i$；
• 累加 $(j - i)$ 到总答案中。
• 时间复杂度：排序耗时 $\mathcal{O}(n \log n)$，双指针扫描过程中 $i$ 和 $j$ 各自最多向前移动 $n$ 次，扫描耗时 $\mathcal{O}(n)$，整体时间复杂度为 $\mathcal{O}(n \log n)$。

3. 另一种优化思路：排序 + 二分查找

除了双指针，利用已排序数组的单调性，还可以使用二分查找直接定位右边界：

• 对于每个奶牛 $p[i]$，利用 C++ STL 的 std::upper_bound 在区间 $[i + 1, n - 1]$ 中查找第一个严格大于 $p[i] + d$ 的位置 it；
• 那么合法奶牛的下标范围即为 $[i + 1, \text{it} - p.\text{begin}() - 1]$，数量为 it - (p.begin() + i + 1)；
• 时间复杂度：排序 $\mathcal{O}(n \log n)$，对 $n$ 个位置各执行一次二分查找 $\mathcal{O}(n \log n)$，整体时间复杂度同样为 $\mathcal{O}(n \log n)$。

⚠️ 核心易错点分析

1. 数据溢出陷阱（必须使用 long long）

• $n$ 最大为 $10^6$；
• 在极端情况下（例如所有奶牛坐标相同或都在距离 $d$ 范围内），相互可听到的总对数可达： $\dfrac{n(n-1)}{2} = \dfrac{10^6 \times (10^6 - 1)}{2} \approx 5 \times 10^{11}$
• C++ 中标准 32 位整型 int 的最大值约为 $2.14 \times 10^9$。$5 \times 10^{11}$ 远超 int 范围，若使用 int 存储答案会产生整型溢出（变成负数或错误值）。
• 因此统计答案的变量 ans 必须声明为 long long 类型！

2. I/O 输入输出效率

• $n = 10^6$ 属于百万级的大规模数据输入，默认的 std::cin 速度较慢可能引起超时。
• 建议在 main 函数开头添加快速输入输出语句：
  CPP

  📋 复制代码

  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  

示例代码

方法一：排序 + 双指针扫描（推荐，效率最高）

#include <algorithm>
#include <iostream>
#include <vector>

using namespace std;

int main() {
    // 开启 I/O 加速
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, d;
    cin >> n >> d;

    vector<int> p(n);
    for (int i = 0; i < n; ++i) {
        cin >> p[i];
    }

    // 1. 坐标升序排序
    sort(p.begin(), p.end());

    // 2. 双指针扫描统计
    long long ans = 0; // 必须使用 long long 防止溢出
    int j = 0;

    for (int i = 0; i < n; ++i) {
        // 右指针向右滑动，直到超出距离 d 或到达边界
        while (j + 1 < n && p[j + 1] - p[i] <= d) {
            ++j;
        }
        // 与当前奶牛 i 配对的合法奶牛数为 j - i
        ans += (j - i);
    }

    cout << ans << "\n";

    return 0;
}

方法二：排序 + STL upper_bound 二分查找

#include <algorithm>
#include <iostream>
#include <vector>

using namespace std;

int main() {
    // 开启 I/O 加速
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, d;
    cin >> n >> d;

    vector<int> p(n);
    for (int i = 0; i < n; ++i) {
        cin >> p[i];
    }

    // 1. 坐标升序排序
    sort(p.begin(), p.end());

    // 2. 对每个元素二分查找最远合法右边界
    long long ans = 0; // 必须使用 long long

    for (int i = 0; i < n; ++i) {
        // 在 [i + 1, n) 范围内查找第一个 > p[i] + d 的位置
        auto it = upper_bound(p.begin() + i + 1, p.end(), p[i] + d);
        // 合法区间为 [p.begin() + i + 1, it)
        ans += (it - (p.begin() + i + 1));
    }

    cout << ans << "\n";

    return 0;
}

复杂度对比与总结

备考技巧归纳：

1. 在处理一维无序数对条件匹配问题时，“先排序使其具备单调性” 是将 $\mathcal{O}(n^2)$ 降低到 $\mathcal{O}(n \log n)$ 或 $\mathcal{O}(n)$ 的关键通用技巧。
2. 只要两端点存在同向单调关系，优先使用 双指针（滑动窗口/尺取法），可以省去二分的 $\log n$ 查找开销。
3. 凡是涉及数对数量累加（最大可能达 $\approx \dfrac{n^2}{2}$）的题目，计数变量务必使用 long long。