P1102 A-B 数对

朴素#

枚举所有的数对 $(a_i,a_j),\ i\ne j$，判断是否等于 $C$ 并计数。

for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)
if(i!=j&&a[i]-a[j]==C)ans++;

复杂度 $O(n^2)$，能拿 75 分。

优化#

考虑什么样的数对 $(a_i,a_j)$ 能满足 $a_i-a_j=C$.

如果我们将输入的所有数字 $a_i$ 对应到数轴上的点，那么就相当于求有多少对点距离恰好为 $C$.

这时候，我们发现朴素算法浪费了很多枚举。实际上，当我们枚举到 $a_i$ 时，不需要把所有 $a_j\ne a_i$ 都试一遍，而只需要知道数轴上 $a_j-C$ 的位置有几个点。

排序+双指针#

刚刚的分析可以转化为以下思路： 先将 $\{a_i\}$ 升序排序，然后使用两个指针 $i,j$ 从 $1$ 开始向右滑动。 每次先 $i \gets i+1$，然后不断 $j \gets j+1$ 直到 $a_j \ge a_i-C$，然后检查 $a_j=a_i-C$ 是否成立。

sort(a+1,a+n+1);
for(int i=1,j=1;i<=n;i++)
{
	while(a[j]<a[i]-C)j++;
	if(a[j]==a[i]-C)ans++;
}

但是这样写无法处理 $a_i$ 中含有重复数字的情况，因此需要做一些调整：

sort(a+1,a+n+1);
for(int i=1,j=1,icnt,jcnt;i<=n;i++)
{
	icnt=1;
	jcnt=0;
	while(a[i+1]==a[i])
	{
		icnt++;
		i++;
	}
	while(a[j]<a[i]-C)j++;
	while(j<i&&a[j]==a[i]-C)
	{
		jcnt++;
		j++;
	}
	ans+=icnt*jcnt;
}

复杂度 $O(n\log n)$，其中排序 $O(n\log n)$，双指针部分 $O(n)$，已经足够优秀，可以通过本题。

计数排序#

实际上，更加符合直觉的做法是直接开一个值域大小的数组 $cnt_x$ 扮演数轴，记录某个数字 $x$ 出现过几次。比如 $a_i=5$ 出现过 3 次，那么 $cnt_{a_i}=cnt_5=3$.

然后遍历所有数字 $a_i$，则能与其配对的数的个数就是 $cnt_{a_i+C}$.（本题 $C>0$，如果允许 $C=0$ 则需要特判 $cnt_{a_i+C} - 1$）。

for(int i=1;i<=n;i++)cnt[a[i]]++;
for(int i=1;i<=n;i++)ans+=cnt[a[i]+C];

由于没有排序（或者说，使用了计数排序这个“不基于比较的排序”），复杂度是 $O(n)$.

然而，这道题的值域 $2^{30}$ 过大，$cnt$ 数组开不了这么大。如果使用这种方法，一种可行方案是配合离散化 ↗，复杂度变回 $O(n\log n)$.

哈希#

哈希，可以理解为一种广义的离散化（或者反过来，离散化是一种特殊的哈希）。它的作用是将稀疏的、值域很大的数据映射到较小的值域上。离散化在此基础上要求保留数据之间原本的大小关系。

使用合适的哈希配合上述计数排序，可以做到 $O(n)$ 的复杂度.

以下使用 STL 的 map 容器实现哈希：

map<int,int>cnt;
//...
for(int i=1;i<=n;i++)
{
	if(cnt.find(a[i])==cnt.end())
		cnt.insert({a[i],1});
	else
		cnt[a[i]]++;
}
for(int i=1;i<=n;i++)
	if(cnt.find(a[i]+C)!=cnt.end())
		ans+=cnt[a[i]+C];

最后，本题数据范围超过 int，请开 long long.