题目描述

出题是一件痛苦的事情！

相同的题目看多了也会有审美疲劳，于是我舍弃了大家所熟悉的 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×1e5

保证所有输入数据绝对值小于 2^{30}

2017/4/29 新添数据两组

 

比较水的一道题，重点讲一下map,lower_bound,upper_bound的使用

map

定义map<a,b>，a,b是数据类型，包括但不限于int等数字类型,string类，char类，甚至是stl内的其他类型，比如栈，堆，队列等等等等，map会建立这两个数据类型间的一一映射

在这个题里，map作为常规数组桶的上位替代，极大的优化了空间

lower_bound&lower_bound

定义lower_bound(a+1,a+1+n,x)-a，返回值代表，在数组a中，从1到n的范围内，第一个小于等于x的数字

定义upper_bound(a+1,a+1+n,x)-a，返回值代表，在数组a中，从1到n的范围内，第一个小于x的数字

由于本质是二分查找，因此这两个函数都需要保证数组中的数是不递减序列

 

说一下思路

核心思路是把a-b=c转化为a=b+c，在此基础上延伸处两个思路

第一个思路是桶排

o(n)的枚举一遍b，只要bus[b+c]不为空就把bus[b]*bus[b+c]加到答案里

第二个思路是排序+lower_bound+upper_bound

同样o(n)的枚举一遍b，用upper_bound和lower_bound去找b+c，upper_bound减去lower_bound的结果就是b+c这个数字的个数，累加到答案

 

代码如下

#include<bits/stdc++.h>
using namespace std;
long long a[200005],n,c,ans;
map<long long,long long> m;
int main() 
{
        cin >> n >> c;
        for(int i=1;i<=n;i++) {
            cin >> a[i];
            m[a[i]]++;
            a[i]+=c;    
        } 
        for(int i=1;i<=n;i++) ans+=m[a[i]];
        cout << ans << endl;
        return 0;
}