思路:
查找A-B = C的对数,则A = B+C,等价于枚举B,查找,数组中有多少个等于B+C的个数,再累加起来
upper_bound():返回的是被查序列中第一个大于查找值得位置;
lower_bound():返回的是被查序列中第一个大于等于查找值的位置
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int maxn = 2e5+7;
LL num[maxn];
LL cnt = 0;
LL n,c;
int main()
{
cin>>n>>c;
for(int i=1;i<=n;i++)
{
cin>>num[i];
}
sort(num+1,num+n+1);
//枚举B
LL ans = 0;
for(LL i=1;i<=n;i++)
{
LL add = num[i] + c;
LL pos = lower_bound(num+1,num+n+1,add)-num;//返回的是数组中第一个大于等于add的位置
if(pos==n+1) continue;//没有数值等于B+C的情况
else
{
LL p = upper_bound(num+1,num+n+1,add)-num;//返回大于add的下标
ans += p - pos;
}
}
printf("%lld\n",ans);
return 0;
}