题目：
P1102 A-B 数对 - 洛谷 | 计算机科学教育新生态
题目背景
出题是一件痛苦的事情！
相同的题目看多了也会有审美疲劳，于是我舍弃了大家所熟悉的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 新添数据两组
思路：
1.A-B=C，我们可以已知A,C。转化一下就是B=A-C。在数组中找到B个数就是成功匹配的数对，由于这个是连续单调的数组，并且可能会出现多个B，所以我们只需要找到第一个出现B和最后一个出现的B的下标。相减再+1就是B成功匹配的次数。
2.用二分还是太麻烦了，记得要先排序。这种题我更喜欢用哈希表，之前用map写过。有兴趣的可以看看。
代码如下：
#include<iostream>
#include<unordered_set>
#include<algorithm>
using namespace std;
typedef long long ll;
const ll L = 2*1e5+10;
ll N,C;
ll arr[L];
bool mem[L];
bool is_first(ll num,ll k)
{
if(num < k)
return true;
else
return false;
}
bool is_final(ll num,ll k)
{
if(num <= k)
return true;
else
return false;
}
int find_first(ll arr[],ll len,ll k)//找到第一个出现的数字k位置
{
ll l = 0,r = len + 1;
while(l + 1 < r)
{
ll mid = (l + r) / 2;
if(is_first(arr[mid],k))
l = mid;
else
r = mid;
}
if(arr[r] == k)
return r;
else
return -1;
}
ll find_final(ll arr[],ll len,ll k)//找到最后一个出现的数字k位置
{
ll l = 0,r = len + 1;
while(l + 1 < r)
{
ll mid = (l + r) / 2;
if(is_final(arr[mid],k))
l = mid;
else
r = mid;
}
if(arr[l] == k)
return l;
else
return -1;
}
int main(void)
{
//缩短输入输出的时间可以不写
ios :: sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
ll cnt = 0;
cin >> N >> C;
for(ll i = 1 ; i <= N ; i++)
{
cin >> arr[i];
}
sort(arr+1,arr+1+N);
for(ll i = 1 ; i <= N ; i++)
{
if(find_first(arr,N,arr[i] - C) == -1)
continue;
else//第一次找到了
{
ll first,final;
first = find_first(arr,N,arr[i] - C);
// cout << arr[i] - C <<"第一个下标：" << first << endl;
final = find_final(arr,N,arr[i] - C);
// cout << arr[i] - C << "最后一个下标：" << final << endl;
cnt = cnt + final - first + 1;
}
}
cout << cnt;
return 0;
} 