问题描述
定义求和问题如下:给定4组整数A,B,C,D,找到有多少四元组(a,b,c,d)∈A×B×C×D,满足条件a+b+c+d=0。此问题中，假设A,B,C,D具有相同的大小n。
输入数据
输入包含多组测试数据。每组测试数据的第一行包含一个整数n，表示A,B,C,D的元素个数(n<=4000)。接下来n行每行4个整数，分别属于A,B,C,D,每个整数的大小在-228~228之间。
输出要求
对于每组测试数据，输出满足条件的四元组的个数。
输入样例
6 -45 22 42 -16 -41 -27 56 30 -36 53 -37 77 -36 30 -75 -46 26 -38 -10 62 -32 -54 -6 45
输出样例
5
解题思路
将问题转化为两组整数的问题。首先枚举出a、b两组所有可能的和sum1,以及c、d两组所有可能的和sum2，将这两组和看成新的组数，然后根据给定两组和为0，对于sum1中每一个数sum1[i],判断-sum1[i]是否在sum2中。即问题转化为查找问题，可以使用二分查找加快查找速度。首先对sum1,sum2元素排序，从小到大枚举每一个元素sum1[i]，使用二分查找判断-sum1[i]是否在数组中，然后计算出现的次数。数组中可能会出现相同的元素，所以采用变形的二分法，在有重复元素的数组中返回小于或等于目标元素的最大元素，若返回元素等于目标元素，则沿着数组计数该元素出现的次数。采用左右都是闭区间的区间规则。
代码
#include<iostream>
#include<algorithm>
using namespace std
;
int Sum1
[10000006],Sum2
[10000006];
int a
[4001],b
[4001],c
[4001],d
[4001];
int t
=0;
int FindCount(int target
)
{
int l
=0,h
=t
-1,num
=0;
while(l
<h
)
{
int mid
=l
+(h
-l
)/2;
if(target
<=Sum2
[mid
])
{
h
=mid
;
}
else
{
l
=mid
+1;
}
}
while(Sum2
[l
]==target
&&l
<t
)
{
num
++;
l
++;
}
return num
;
}
int main()
{
int n
;
cin
>>n
;
for(int i
=0;i
<n
;i
++)
{
cin
>>a
[i
]>>b
[i
]>>c
[i
]>>d
[i
];
}
for(int i
=0;i
<n
;i
++)
{
for(int j
=0;j
<n
;j
++)
{
Sum1
[t
]=a
[i
]+b
[j
];
Sum2
[t
]=c
[i
]+d
[j
];
t
++;
}
}
sort(Sum1
,Sum1
+t
);
sort(Sum2
,Sum2
+t
);
int num
=0;
for(int i
=t
-1;i
>=0;i
--)
{
num
+=FindCount(-Sum1
[i
]);
}
cout
<<num
<<endl
;
return 0;
}
