题目背景

出题是一件痛苦的事情！

相同的题目看多了也会有审美疲劳，于是我舍弃了大家所熟悉的 A+B Problem，改用 A-B 了哈哈！

题目描述

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

输入格式

输入共两行。

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

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

输出格式

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

输入输出样例

输入 #1复制

4 1
1 1 2 3

输出 #1复制

3

说明/提示

对于 75% 的数据，1≤N≤2000。

对于 100% 的数据，1≤N≤2×105，0≤ai​<230，1≤C<230。

2017/4/29 新添数据两组

思路：

首先，数组不一定是无序的，遍历整个数组太浪费时间了，可以先将数组排序，用sort就行。

第一遍的思路是遍历每一个数组元素，寻找和该元素匹配的元素个数。因为数组是有序的（刚开始我设置为降序），那么只需从该元素的位置开始，向后遍历寻找，当找到距离之差大于C时即可跳出循环，虽然也不用每次遍历完数组剩余部分，但是仍然存在很多不必要的查找操作，增大了时间的开销。假如C的值很大，取10000，最坏的情况，我们可能要不断地向后查找可能将近10000多次甚至更多，才能找到第一个符合条件的值，而这之前的查找都是不必要的。

那么，能否直接查找到目标值呢，但很多函数，只能告诉你目标值是否存在，而不能告诉你有几个目标值（可能有多个），那么我们需要查找到第一个符合条件的元素下标和第一个不符合条件的下标，二者相减即可得到中间包含的符号条件的元素个数，而不必要去一一遍历那些无关元素。

STL自带的二分函数——upper_bound和lower_bound，这两个函数的作用是二分查找一个数在数组中出现的位置，区别如下：

- upper_bound：返回第一个大于搜索数的位置

- lower_bound：返回第一个大于等于搜索数的位置

  - 函数的用法：lower_bound(a.begin(),a.end(),x) 返回第一个大于等于x的数的地址，而由于是地址，在最后要-a（也就是减去数组首地址）

TLE代码：

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


int main() {
	int n;
	long long int c;
	cin >> n >> c;
	long long int arr[n];
	for (int i = 0; i < n; i++) {
		cin >> arr[i];
	}
	sort(arr, arr + n, greater<int>());
	int ans = 0;
	for (int i = 0; i < n; i++) { //遍历每一个数是否存在数对
		int j = i;
		while (arr[i] - arr[j] <= c && j < n) {
			if (arr[i] - arr[j] == c)
				ans++;
			j++;
		}
	}
	cout << ans;
	return 0;
}

两个测试点没过，超时了。

AC代码：

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


int main() {
	int n;
	long long int c;
	cin >> n >> c;
	long long int arr[n];
	for (int i = 0; i < n; i++) {
		cin >> arr[i];
	}
	sort(arr, arr + n);
	long long int ans = 0;
	//int j=0;
	for (int i = 0; i < n - 1; i++) { //遍历每一个数是否存在数对
		ans += ((upper_bound(arr, arr + n, arr[i] + c) - arr) - (lower_bound(arr, arr + n, arr[i] + c) - arr));
	}
	cout << ans;
	return 0;
}