A-B 数对（洛谷）

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 <= N <= 2000。
对于 100% 的数据，1 <= N <= 2*10⁵，0 <=a_i <2³⁰，1 <= C < 2³⁰。

代码

#include<bits/stdc++.h>
using namespace std;

// 数组b用于存储输入的正整数序列
int b[1000000];
// n用于存储正整数序列的长度
int n;

// 快速排序函数，用于将数组b的[l, r]区间内的元素进行升序排列
void quick_sort(int b[], int l, int r)
{
    // 如果l大于等于r，说明区间没有元素或者只有一个元素，不需要排序，直接返回
    if(l >= r) return;
    
    // 初始化双指针i、j和基准值x
    int i = l - 1, j = r + 1, x = b[l + r >> 1];
    
    // 分区操作
    while(i < j)
    {
        // 移动左指针，找到第一个大于等于基准值的元素
        do i++; while(b[i] < x);
        // 移动右指针，找到第一个小于等于基准值的元素
        do j--; while(b[j] > x);
        // 如果左右指针没有相遇，交换元素
        if(i < j) swap(b[i], b[j]);
    }
    
    // 对左半部分递归排序
    quick_sort(b, l, j);
    // 对右半部分递归排序
    quick_sort(b, j + 1, r);
}

// 归并排序函数，用于将数组b的[l, r]区间内的元素进行升序排列
void merge_sort(int b[], int l, int r)
{
    // 如果l大于等于r，不需要排序
    if(l >= r) return;
    
    // 计算中点
    int mid = l + r >> 1;
    // 递归排序左半部分
    merge_sort(b, l, mid);
    // 递归排序右半部分
    merge_sort(b, mid + 1, r);
    
    // 合并两个有序数组
    int k = 0, i = l, j = mid + 1;
    while(i <= mid && j <= r)
    {
        if(b[i] <= b[j]) tmp[k++] = b[i++];
        else tmp[k++] = b[j++];
    }
    
    // 将剩余的元素添加到tmp数组中
    while(i <= mid) tmp[k++] = b[i++];
    while(j <= r) tmp[k++] = b[j++];
    
    // 将合并后的数组复制回原数组
    for(i = l, j = 0; i <= r; i++, j++) b[i] = tmp[j];
}

// 查找函数find1，用于在数组b中找到第一个大于等于a的元素的索引
int find1(int a)
{
    int l = 0, r = n - 1;
    while(l < r)
    {
        int mid = l + r >> 1;
        if(b[mid] >= a) r = mid;
        else l = mid + 1;
    }
    if(b[l] == a) return l;
    return -1;
}

// 查找函数find2，用于在数组b中找到最后一个小于等于a的元素的索引
int find2(int a)
{
    int l = 0, r = n - 1;
    while(l < r)
    {
        int mid = l + r + 1 >> 1;
        if(b[mid] <= a) l = mid;
        else r = mid - 1;
    }
    if(b[r] == a) return r;
    return -1;
}

// 主函数
int main()
{
    // 读入正整数序列的长度n和差值c
    int c;
    cin >> n >> c;
    // count用于统计满足条件的数对个数
    long long count = 0;//int会爆范围 
    int i;
    // 读入序列到数组b
    for(i = 0; i < n; i++)
        cin >> b[i];
    
    // 对数组b进行快速排序
    quick_sort(b, 0, n - 1);
    // 下面的merge_sort函数被注释掉了，选择快速排序进行实际的排序操作
    // merge_sort(b, 0, n - 1);
    
    // 遍历数组b，寻找满足条件的数对
    for(i = 0; i < n; i++)//枚举B的下标，使得A-B=C，变为A=B+C 
    {
        int a = b[i] + c;
        int res1 = find1(a); // 查找满足条件的A的起始索引
        if(res1 == -1) // 如果没有找到满足条件的A，继续下一轮循环
            continue;
        else
        {
            int res2 = find2(a); // 查找满足条件的A的结束索引
            count += res2 - res1 + 1; // 将找到的A的数量累加到count中
        }
    }
    // 输出满足条件的数对个数
    cout << count << endl;
    return 0;
}

部分代码解析

??当我们查找满足 A - B = C 的数对时，一旦确定了一个B的值，我们就需要找到所有可能的A的值。在排序后的数组中，A的值必须是B+C。函数find1找到了第一个等于A的元素的位置（也就是最小的索引），而函数find2找到了最后一个等于A的元素的位置（也就是最大的索引）。

??例如，假设我们有以下排序后的数组a：

??a = [1, 2, 3, 3, 4, 5, 6]

??我们要找到所有满足 A - B = C 的数对，给定 C = 1。如果我们选择 B = 2（即a[1]），那么 A 应该等于 3（即 B + C = 2 + 1）。
??现在我们使用find1在数组a中找到值为A=3的第一个位置，假设是a[2]。然后，我们使用find2找到值为A=3的最后一个位置，假设是a[3]。这意味着在数组a的索引2和3处，元素的值都是3。

??a[2] = 3
??a[3] = 3

??所以，对于 B = 2，我们找到了两个满足条件的A。因此，对于这个B，满足 A - B = C 的数对的数量是：

??res2 - res1 + 1 = 3 - 2 + 1 = 2

??这样我们就计算出了从起始位置到结束位置所有满足条件的A的数量。这个计算过程对每一个可能的B值都要重复执行，然后把所有找到的数量累加到count中，最终得到满足条件的总数对数量。