P1102 A-B 数对题解

题目要求我们找到所有满足条件 $A - B = C$ 的数对的数量。这里的关键点在于如何高效地查找这些数对。

步骤分析

1. 读取输入:

   • 读取两个整数 $N$ 和 $C$，分别代表数组的长度和目标差值。
   • 接着读取一个包含 $N$ 个正整数的数组。

2. 排序:

   • 对数组进行排序，这样可以利用二分查找来快速定位某个元素是否存在。

3. 二分查找:

   • 对于每一个元素 $a[i]$，我们需要寻找是否存在另一个元素 $b[j]$ 使得 $a[i] - b[j] = C$。
   • 这意味着对于每个 $a[i]$，我们要查找是否存在一个 $b[j] = a[i] - C$。
   • 使用二分查找可以有效地确定这样的元素是否存在，并且可以在有序数组中快速定位其位置。

4. 计数符合条件的数对:

   • 如果找到了符合条件的 $b[j]$，那么从第一个符合的位置到最后一个符合的位置的所有数对都符合条件。
   • 计算这些数对的数量并累加到答案中。

5. 输出结果:

   • 最后输出总的数对数量。

代码实现

以下是按照上述步骤编写的完整C++代码：

#include<bits/stdc++.h>
using namespace std;
int a[200000];
long long ans;
int main(){
    int n, c;
    cin >> n >> c;
    for(int i = 0; i < n; i++){
        cin >> a[i];
    }
    sort(a, a + n);
    for(int i = 0; i < n; i++){
        int x = a[i] - c;
        int l = -1, r = n;
        while(l + 1 < r){
            int mid = (l + r) / 2;
            if(a[mid] > x){
                r = mid;
            }else{
                l = mid;
            }
        }
        if(a[l] != x){
            continue;
        }
        int last = l;
        l = -1, r = n;
        while(l + 1 < r){
            int mid = (l + r) / 2;
            if(a[mid] < x){
                l = mid;
            }else{
                r = mid;
            }
        }
        ans += (last - r + 1);
    }
    cout << ans;
    return 0;
}