poj2785—总和为零的四元组数java

题目描述

给定两个长度均为 $n$ 的数组 $A,B$，其中 $A$ 数组中的元素两两不同，$B$ 数组中元素也两两不同。

定义 $A$ 数组的第 $i$ 个元素为 $a_i$，$B$ 数组的第 $i$ 个元素为 $b_i$。定义一个四元组 $(i,j,k,l)$ 符合条件当且仅当 $1 \leq i < j \leq n$，$1 \leq k < l \leq n$，$$ a_i+b_j=k+l $$ 问有多少个符合条件的四元组。

输入

输入的第一行为一个整数 $n$，表示 $A$ 和 $B$ 数组的长度。 接下来 $n$ 行，第 $i$ 行包含两个整数 $A_i$ 和 $B_i$。

输出

输出一行，一个整数，表示符合条件的四元组个数。

输入样例

3
1 1
2 2
3 3

输出样例

6

提示

$1 \leq n \leq 1500$，$1 \leq A_i,B_i \leq 10^9$

这一题要求解符合条件的四元组。其中有一个直观的想法就是将四元组分类讨论，如下所示：

$$a_i + b_j = k + l$$

分类讨论，当 $i < k, j < l$ 时就是一种方案，当 $i > k, j > l$ 时是另一种情况。

因此，对于每一种 $a_i + b_j$ 的和，记录下它的出现次数，同时记录下这个和所对应的 $i, j$ 的值。在计算的过程中，如果遇到相同的和的时候，再次遇到时是可以直接忽略的，因为等式是对称的。

统计符合条件的四元组当然要对和进行枚举，但是值得注意的是，在构造符合条件的 $k, l$ 的时候，数组 $C$ 和 $D$ 的记录顺序是无关紧要的，因为等式 $a_i + b_j = k + l$ 已经将每个数字都制约了，它们可以出现任意的顺序。因此，在统计 $C$ 和 $D$ 对于计算答案来说是无区别的。

这一题值得特别注意的是，当数组中有数据的时候，要注意考虑到数据越界可能导致结果错误。在本题中，由于 $a_i, b_j$ 的上限是 $10^9$，因此 $a_i + b_j$ 的上限最大可能会达到 $2 \times 10^9$，因此在计算时一定要使用 long long 类型，否则很容易产生错误。