洛谷刷题C++语言 | P1102 A-B数对

学习C++从娃娃抓起！记录下洛谷C++学习和备考过程中的题目，记录每一个瞬间。

附上汇总贴：洛谷刷题C++语言 | 汇总_热爱编程的通信人的博客-CSDN博客

【题目描述】

给出一串正整数数列以及一个正整数 C，要求计算出所有满足 A?B=C 的数对的个数（不同位置的数字一样的数对算不同的数对）。

【输入】

输入共两行。

第一行，两个正整数 N,C。

第二行，N 个正整数，作为要求处理的那串数。

【输出】

一行，表示该串正整数中包含的满足 A?B=C 的数对的个数。

【输入样例】

4 1
1 1 2 3

【输出样例】

3

【代码详解】

#include <bits/stdc++.h>
using namespace std;
int n, c, a[200005], sum;
long long ans=0;
int findleft(int q)  // 二分查左值
{
    int l=1, r=n+1;
    while (l<r) {
        int mid = l + (r-l)/2;
        if (a[mid]>=q) r = mid;
        else l = mid+1;
    }
    if (a[l]==q) {
        return l;
    } else return 0;
}
int findright(int q)  // 二分查右值
{
    int l=1, r=n+1;
    while (l<r) {
        int mid = l + (r-l)/2;
        if (a[mid]<=q) l = mid+1;
        else r = mid;
    }
    if (a[l-1]==q) {
        return l-1;
    } else return 0;
}

int main()
{
    cin >> n >> c;
    for (int i=1; i<=n; i++) {
        cin >> a[i];
    }
    sort(a+1, a+n+1);
    for (int i=1; i<=n; i++) {
        //枚举B，使用二分查找满足a[j]==a[i]+c
        int q = a[i]+c;
        if (findleft(q)==0 && findright(q)==0) sum=0;
        else sum = findright(q) - findleft(q) + 1;
        ans += sum;
    }
    cout << ans << endl;
    return 0;
}

【运行结果】

4 1
1 1 2 3
3