写出暴力导致TLE的解法代码

当然可以。对于这道题，最直观的暴力解法就是使用两层循环，不进行任何优化，直接枚举所有的数对 $(A, B)$。

这种解法的时间复杂度是 $O(N^2)$，当 $N$ 的规模达到 $2 \times 10^5$ 时，$N^2$ 约为 $4 \times 10^{10}$，这会远远超过一般在线评测系统（OJ）每秒 $10^8$ 次左右的计算能力上限，因此会导致超时 (Time Limit Exceeded, TLE)。

写出并理解 TLE 版本是学习算法优化的第一步，因为它能让你清晰地看到问题的“朴素”解法是什么，从而思考如何针对性地进行优化。

暴力 $O(N^2)$ TLE 代码 (C++)

这个版本的代码思路非常简单：

1. 读入所有数据。
2. 第一层循环 for i from 0 to n-1，枚举每一个数 a[i] 作为数对中的 $A$。
3. 第二层循环 for j from 0 to n-1，枚举每一个数 a[j] 作为数对中的 $B$。
4. 为了避免把自己和自己组成数对（除非题目允许且有多个相同数字），加上判断 if (i == j) continue;。
5. 判断 if (a[i] - a[j] == C) 是否成立，如果成立，则计数器加一。
6. 输出最终的计数器。

#include <iostream>
#include <vector>

// 使用 long long 来存储计数器，防止结果溢出
// 虽然在这份 TLE 代码中可能遇不到那么大的结果，但这是个好习惯
using ll = long long;

int main() {
    // 尽管会 TLE, IO 优化还是可以写上
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    int n;
    ll c;
    std::cin >> n >> c;

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

    ll count = 0;

    // 外层循环，枚举每个元素 a[i] 作为 A
    for (int i = 0; i < n; ++i) {
        // 内层循环，枚举每个元素 a[j] 作为 B
        for (int j = 0; j < n; ++j) {
            
            // 题目要求：“不同位置的数字一样的数对算不同的数对”
            // 这意味着 a[0] 和 a[1] 即使值相同，也是不同的位置。
            // 因此，我们不需要跳过 i == j 的情况，因为题目并没有说A和B必须是不同位置的数
            // 如果题目要求是不同位置，则需要 if(i == j) continue;
            // 按照题意，a[i] 和 a[i] 自己也可以组成一对，如果 a[i] - a[i] == C
            
            // 检查差值是否等于 C
            // 注意：a[i] 和 c 的类型可能是 int 和 long long，
            // 为了避免隐式转换可能带来的问题，显式地进行类型转换
            if ((ll)a[i] - (ll)a[j] == c) {
                count++;
            }
        }
    }

    std::cout << count << std::endl;

    return 0;
}

为什么这份代码会 TLE？

• 循环次数：代码的核心是两层嵌套的 for 循环。外层循环执行 $N$ 次，内层循环也执行 $N$ 次。总的判断次数是 $N \times N = N^2$ 次。
• 数据规模：
  • 对于 $75\%$ 的数据，$N \le 2000$。$N^2 = 4 \times 10^6$，这个计算量在 1 秒内通常是可以接受的。所以这份代码能通过一部分测试点。
  • 对于 $100\%$ 的数据，$N \le 2 \times 10^5$。$N^2 = (2 \times 10^5)^2 = 4 \times 10^{10}$。这个计算量是巨大的，远远超出了时限。

教练点评： 这份代码就是你思考这道题时的“原点”。所有更优的算法，无论是排序+二分还是排序+双指针，都是为了优化内层的这一个循环——将原本 $O(N)$ 的查找过程，降低到 $O(\log N)$（二分）或者均摊 $O(1)$（双指针）。这就是算法优化的本质。

好的，没问题。

这里提供一个功能完整的数据生成器。它会生成 10 组测试数据（1.in/1.out 到 10.in/10.out），并且测试点设计考虑了各种边界情况和数据分布，非常适合用于搭建 OJ。

数据生成器功能说明

1. 内置标准解法：生成器内部包含了 排序 + 二分 的 $O(N \log N)$ 标准解法，用于计算并生成正确的 .out 文件。
2. 覆盖多种情况：
   • Test 1-3: 小规模随机数据，便于手动验证。
   • Test 4: 边界 - 大量重复数字。
   • Test 5: 边界 - 不存在满足条件的数对 (答案为 0)。
   • Test 6: 边界 - 数组已排序（升序）。
   • Test 7: 边界 - 数组逆序。
   • Test 8: 较大规模数据，但数字范围较小（导致大量重复）。
   • Test 9-10: 满数据规模（$N=2 \times 10^5$），随机大数据，测试性能。

数据生成器代码 (generator.cpp)

#include <iostream>
#include <vector>
#include <algorithm>
#include <fstream>
#include <string>
#include <random>
#include <chrono>

using namespace std;

// ==========================================
// 第一部分：标准解题逻辑 (用于生成 .out)
// ==========================================
long long solve_case(int n, long long c, vector<int>& a) {
    sort(a.begin(), a.end());
    long long count = 0;
    for (int i = 0; i < n; ++i) {
        long long target_a = (long long)a[i] + c;
        auto low = lower_bound(a.begin(), a.end(), target_a);
        auto high = upper_bound(a.begin(), a.end(), target_a);
        count += distance(low, high);
    }
    return count;
}

// ==========================================
// 第二部分：数据生成工具
// ==========================================

// 初始化高质量随机数引擎
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

int random_int(int l, int r) {
    uniform_int_distribution<int> dist(l, r);
    return dist(rng);
}

// 生成单个测试点
void generate_data(int case_id, int n, long long max_c, int max_a, string type) {
    string in_file = to_string(case_id) + ".in";
    string out_file = to_string(case_id) + ".out";

    ofstream fout(in_file);

    long long c = random_int(1, max_c);
    fout << n << " " << c << endl;

    vector<int> a(n);
    if (type == "random") {
        for (int i = 0; i < n; ++i) {
            a[i] = random_int(1, max_a);
        }
    } else if (type == "duplicates") {
        // 生成大量重复数字
        int distinct_count = min(n, max(10, n / 10));
        vector<int> choices;
        for(int i=0; i<distinct_count; ++i) choices.push_back(random_int(1, max_a));
        for (int i = 0; i < n; ++i) {
            a[i] = choices[random_int(0, distinct_count - 1)];
        }
    } else if (type == "no_answer") {
        // 构造无解数据，让所有 a[j] - a[i] != c
        // 一个简单方法是让所有数都是奇数，而 c 是偶数
        c = random_int(1, max_c / 2) * 2;
        fout.seekp(0); // 回到文件开头重写
        fout << n << " " << c << endl;
        for (int i = 0; i < n; ++i) {
            a[i] = random_int(0, max_a / 2) * 2 + 1; // 生成奇数
        }
    } else if (type == "sorted") {
        for (int i = 0; i < n; ++i) {
            a[i] = random_int(1, max_a);
        }
        sort(a.begin(), a.end());
    } else if (type == "reversed") {
        for (int i = 0; i < n; ++i) {
            a[i] = random_int(1, max_a);
        }
        sort(a.rbegin(), a.rend());
    }

    // 写入 .in 文件
    for (int i = 0; i < n; ++i) {
        fout << a[i] << (i == n - 1 ? "" : " ");
    }
    fout << endl;
    fout.close();

    // 计算标准答案并写入 .out 文件
    long long result = solve_case(n, c, a);
    ofstream f_ans(out_file);
    f_ans << result << endl;
    f_ans.close();

    cout << "Generated Case " << case_id << ": N=" << n 
         << " [" << type << "] -> Ans=" << result << endl;
}

int main() {
    // 题目约束 N <= 2e5, a < 2^30, C < 2^30
    // 2^30 约 1e9
    const int MAX_VAL = 1e9;

    // Test 1-3: 小数据
    generate_data(1, 10, 10, 20, "random");
    generate_data(2, 50, 20, 100, "random");
    generate_data(3, 100, 50, 200, "random");

    // Test 4: 边界 - 大量重复
    generate_data(4, 2000, 1000, 50, "duplicates");

    // Test 5: 边界 - 构造无解
    generate_data(5, 2000, 1000, 5000, "no_answer");
    
    // Test 6: 边界 - 预先排序
    generate_data(6, 5000, 2000, 10000, "sorted");

    // Test 7: 边界 - 逆序
    generate_data(7, 5000, 2000, 10000, "reversed");

    // Test 8: 较大 N，较小数值范围
    generate_data(8, 50000, 1000, 100, "random");

    // Test 9: 满数据
    generate_data(9, 200000, MAX_VAL, MAX_VAL, "random");

    // Test 10: 满数据，有大量重复
    generate_data(10, 200000, MAX_VAL, 1000, "duplicates");

    cout << "All 10 test cases generated successfully!" << endl;
    return 0;
}

如何使用

1. 将上面的代码保存为 generator.cpp。
2. 使用 C++11 或更高标准的编译器进行编译，例如： g++ generator.cpp -o generator -std=c++11
3. 运行生成的可执行文件： ./generator （在 Linux/macOS 上） generator.exe （在 Windows 上）
4. 程序运行后，当前目录下就会出现 1.in, 1.out, 2.in, 2.out, ..., 10.in, 10.out 这些文件。
5. 将这些文件上传到你的 OJ 系统即可。

你好！我是你的OI教练。

这道 P1102 A-B 数对是一道非常经典的题目，是检验你是否真正理解排序、二分查找和双指针这三大基础算法的试金石。

对于 $100\%$ 的数据 ($N \le 2 \times 10^5$)，一个 $O(N^2)$ 的暴力两层循环枚举是肯定会超时的。我们必须寻求更高效的 $O(N \log N)$ 或 $O(N)$ 的解法。

第一部分：思路提示与解法对比

解法一：排序 + 二分查找 ($O(N \log N)$)

1. 转化问题：我们要找的是 $A - B = C$，这等价于 $A = B + C$。
2. 核心思想：我们可以枚举每一个数作为 $B$，然后去序列中快速地寻找是否存在一个数 $A$ 等于 $B+C$。
3. 如何“快速寻找”？
   • 如果序列是无序的，我们每次寻找都得遍历一遍，总复杂度还是 $O(N^2)$。
   • 关键：如果我们先将整个序列排序，那么对于每一个 $B$，寻找 $A=B+C$ 的过程就可以用二分查找来完成，时间是 $O(\log N)$。
4. 处理重复数字：
   • 如果序列中有重复的数字，比如 1 1 2 3，C=1。
   • 当我枚举第一个 1 作为 $B$ 时，我需要在剩下的序列里找 $A=1+1=2$。二分查找能找到一个 2。
   • 但我怎么知道有多少个 2 呢？
   • 技巧：在 C++ STL 中，std::lower_bound 找的是第一个不小于目标值的迭代器，std::upper_bound 找的是第一个大于目标值的迭代器。
   • 那么，upper_bound(A) - lower_bound(A) 的结果，就是序列中等于 A 的元素个数！
5. 算法流程： a. 对整个数组 a 进行排序。 b. 初始化 count = 0。 c. 遍历排序后的数组 a，将每个元素 a[i] 当作 $B$。 d. 计算目标值 target_A = a[i] + C。 e. 在数组 a 中，用 lower_bound 和 upper_bound 查找 target_A 的出现次数，累加到 count 中。 f. 输出 count。

解法二：排序 + 双指针 ($O(N)$，排序后)

这是比二分查找更优的解法，总复杂度也是瓶颈在排序的 $O(N \log N)$。

1. 核心思想：同样先将数组排序。我们用两个指针 i 和 j，都从数组的左端开始。我们希望 a[j] - a[i] 恰好等于 C。

2. 指针移动策略：

   • 初始化 i = 0, j = 0。
   • 当 j < n 时，循环：
     • 计算差值 diff = a[j] - a[i]。
     • 如果 diff == C：说明我们找到了一个可能的数对。但是，可能存在多个 a[i] 和多个 a[j] 都是一样的。我们需要计算有多少个 a[i] 和多少个 a[j]。然后 count += (i的重复个数) * (j的重复个数)。之后移动 i 和 j 到下一个不同的数字。
     • 如果 diff < C：说明 a[j] 太小了，差值不够。我们需要增大 a[j]，所以 j++。
     • 如果 diff > C：说明 a[j] 太大了，差值过头了。我们需要增大 a[i]，所以 i++。

3. 处理重复数字 (更简洁的双指针):

   • 我们先不考虑一次性统计重复个数，而是让指针自然移动。
   • 初始化 i = 0, j = 1。
   • while (j < n):
     • 如果 a[j] - a[i] < C，j++
     • 如果 a[j] - a[i] > C，i++
     • 如果 a[j] - a[i] == C，此时我们找到了一个解。但是，可能有多个 a[j] 都是这个值。我们固定 i，让 j 继续向后走，直到 a[j] 不再是这个值，统计 j 走过的步数，累加到 ans。然后 i++。
   • 这种写法逻辑稍复杂。最简单的双指针是固定一个指针，移动另一个。

   推荐的双指针写法（固定 i，移动 j）：

   long long count = 0;
   int j = 0;
   for (int i = 0; i < n; i++) {
       // 对于每个 a[i] (作为 B)，我们希望找到 a[j] (作为 A)
       // a[j] = a[i] + C
       // j 只需要从 i 的右边开始找，并且 j 是单调不减的
       while (j < n && a[j] < a[i] + C) {
           j++;
       }
       
       // 此时 a[j] >= a[i] + C
       // 如果 a[j] == a[i] + C，说明找到了
       if (j < n && a[j] == a[i] + C) {
           // 需要统计有多少个 a[j]
           int temp_j = j;
           while (temp_j < n && a[temp_j] == a[i] + C) {
               count++;
               temp_j++;
           }
       }
   }
   

   这个版本是 $O(N^2)$ 的，因为 temp_j 可能会重复扫描。真正的 $O(N)$ 双指针需要更巧妙的设计。

   真正的 $O(N)$ 双指针 (处理重复数字)：

   long long ans = 0;
   for(int i = 0, j = 0; i < n; i++) {
       while(j < n && a[j] < a[i] + C) j++;
       // 此时 a[j] 是第一个 >= a[i] + C 的数
       
       // 我们要找的是 == a[i] + C 的数
       int j2 = j;
       while(j2 < n && a[j2] == a[i] + C) j2++;
       
       // 从 j 到 j2-1 都是满足条件的 A
       ans += j2 - j;
   }
   

   这个 j 指针只会向右移动，不会回溯，所以总复杂度是 $O(N)$。

第二部分：预备知识点总结

1. std::sort：必须掌握，是绝大多数高效算法的前提。
2. std::lower_bound 和 std::upper_bound：二分查找的利器，尤其擅长处理重复元素。
3. 双指针 (Two Pointers)：一种线性扫描的优化技巧，核心是利用单调性。
4. 数据类型：注意 N 最大 $2 \times 10^5$，数对的个数可能超过 int 的范围，要用 long long 存储结果。

第三部分：代码实现 (两种解法)

解法一：排序 + 二分查找

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

int main() {
    // 竞赛标准 IO 优化
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    int n;
    long long c;
    std::cin >> n >> c;

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

    // 步骤1: 排序
    std::sort(a.begin(), a.end());

    long long count = 0;

    // 步骤2: 遍历每个元素作为 B
    for (int i = 0; i < n; ++i) {
        long long b = a[i];
        long long target_a = b + c;

        // 步骤3: 使用 lower_bound 和 upper_bound 查找 target_a 的个数
        // lower_bound 找到第一个 >= target_a 的位置
        auto low = std::lower_bound(a.begin(), a.end(), target_a);
        
        // upper_bound 找到第一个 > target_a 的位置
        auto high = std::upper_bound(a.begin(), a.end(), target_a);
        
        // 两者之差就是等于 target_a 的元素个数
        count += std::distance(low, high);
    }

    std::cout << count << std::endl;

    return 0;
}

解法二：排序 + 双指针 (最终优化版)

这个版本更难理解，但是效率更高。

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

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    int n;
    long long c;
    std::cin >> n >> c;

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

    std::sort(a.begin(), a.end());

    long long count = 0;
    
    // i, j 两个指针都从头开始
    // i 枚举 B, j 寻找 A
    for (int i = 0, j = 0; i < n; ++i) {
        // 移动 j，直到 a[j] 至少和 a[i] + C 一样大
        // 因为数组是排序的，j 只需要前进，不需要后退
        while (j < n && a[j] < a[i] + c) {
            j++;
        }
        
        // 此时，a[j] 是第一个 >= a[i] + c 的元素
        // 如果 a[j] 恰好等于 a[i] + c
        if (j < n && a[j] == a[i] + c) {
            // 那么，我们需要知道有多少个 a[i] 和多少个 a[j]
            // 更简单的思路是，我们只统计以当前 a[i] 开头的数对
            // 为了避免重复计算，我们可以先统计 a[i] 的数量
            int i_count = 1;
            while(i + 1 < n && a[i+1] == a[i]){
                i_count++;
                i++;
            }
            
            int j_start = j;
            while(j < n && a[j] == a[i] + c){
                j++;
            }
            int j_count = j - j_start;
            
            // 注意这里 j 指针已经移动到后面了，外层循环的 i 也会跳过重复
            count += (long long)i_count * j_count;
            // 因为 j 已经移动到不满足条件的位置，所以下一个 i 不需要从头找 j
            // 但 j 要回退一点，以便下一个不同的 i 可以从正确的位置开始
            j = j_start;
        }
    }
    // 上述写法比较复杂，我们还是用最经典的二分法思路
    // 真正的 O(N) 双指针不需要回退 j，只需要统计个数
    count = 0;
    for (int i = 0; i < n; ++i) {
        long long target_a = (long long)a[i] + c;
        // 对于每个a[i]，我们找有多少个 a[j] == target_a
        // 这不就是二分法的逻辑吗？
        // 所以本题最简洁的思路就是二分法
        auto low = std::lower_bound(a.begin() + i + 1, a.end(), target_a);
        auto high = std::upper_bound(a.begin() + i + 1, a.end(), target_a);
        count += std::distance(low, high);
    }


    std::cout << count << std::endl;

    return 0;
}

教练修正与最终推荐： 经过分析，对于这道题，“排序 + 二分查找” 的解法不仅在逻辑上最清晰、最不容易出错，而且代码也最简洁。lower_bound 和 upper_bound 内部实现就是二分，它们是解决这类“在有序序列中查找元素个数”问题的标准工具。双指针解法虽然理论上更快（排序后 $O(N)$ vs $O(N \log N)$），但处理重复元素时逻辑容易变得复杂，容易出错。

最终建议：在比赛中，对于这道题，毫不犹豫地使用排序+二分查找。总复杂度 $O(N \log N)$ 对于 $N=2 \times 10^5$ 来说绰绰有余。