【解题报告】洛谷P1102 A-B数对

题目链接

https://www.luogu.com.cn/problem/P1102

思路

我们可以统计数列中每个数字的数量，记录到 cnt[b[i]]cnt[b[i]] 中，作为B

我们把 A−B=CA-B=C 变换一下，就变成了 B+C=AB+C=A

所以我们对于之前统计的东西直接 cnt[b[i]+c]cnt[b[i]+c] ,这个东西直接累加到答案中就可以了

由于值域太大，我们使用一个 stl::map

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <map>
using namespace std;
int n,c;
map<int,int> cnt;
long long a[2000005];
long long ans;
int main()
{
	cin>>n>>c;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];
		cnt[a[i]]++;
	}
	for(int i=1;i<=n;i++)
	ans+=cnt[a[i]+c];
	cout<<ans<<endl;
	return 0;
}