A-B问题 题解

(题目转载自洛谷)

1
2
3
4
5
6
7
8
9
10
题目描述：
给出一串数以及一个数字C，要求计算出所有A-B=C的数对的个数（一样的数对但是数字属于不同的位置，算不同的数对）
输入格式：
输入共两行。
第一行，两个整数N,C。
第二行，N个整数，作为要求处理的那串数。
输出格式：
一行，表示该串数中包含的满则A-B=C的数对的个数
注：1<= N <=2e5
保证所有输入的数据绝对值小于2^30

注意点：答案要开longlong，因为极限数据是100000个1和100000个2，答案会到10的10次方，而int的范围只到2*10的9次方。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
#include<iostream>
using namespace std;

typedef long long LL;
const int N = 1e6;
int q[N];//用来存放那串数
LL num;//要开longlong,会爆int
int value,n,c;
//快排
void quick_sort(int q[], int l, int r) {
    if (l >= r) return;
    int i = l - 1, j = r + 1;
    int x = q[l + r >> 1];
    while (i < j) {
        do i++; while (q[i] < x);
        do j--; while (q[j] > x);
        if (i < j) swap(q[i], q[j]);
    }
    quick_sort(q, l, j); quick_sort(q, j + 1, r);
}

int main() {
    cin>>n>>c;
    for (int i = 0; i < n; i++) cin>>q[i];
    quick_sort(q, 0, n - 1);
    //遍历给出的那串数，一个一个进行查找
    for (int i = 0; i < n; i++) {
    //二分查找，先找满足条件的数的起始位置
        int l = 1, r = n - 1;
        while (l < r) {
            int mid = l + r >> 1;
            if (q[mid] - q[i] >= c) r = mid;
            else l = mid + 1;
        }
        //如果q[l]满足条件，用value记录起始位置，再找满足条件的数的终止位置
        if (q[l] - q[i] == c) {
            value = l;
            int l = 1, r = n - 1;
            while (l < r) {
                int mid = l + r + 1 >> 1;
                if (q[mid] - q[i] <= c) l = mid;
                else r = mid - 1;
            }
            num += l - value + 1;//终止坐标-起始坐标+1得出满足条件的书的个数
        }
    }
    cout << num;
    return 0;
}