四数之和为零 [UVA – 1152] 简析
给四个长度相同的序列，从每个序列中选出一个数字组成一个四元组，有多少个四元组之和为0.
枚举是不可能的，O(N^4)的时间不可接受。两个序列的情况，对于序列a的每个数字，我们可以以总O(NlogN)的时间找到序列b中的数字与a中的那个之和为0，即对a中的x，用二分搜确定-x是否在b中（重复的都要记）。如果是三个序列，可以先将两个序列两两相加，组成一个长为N*N的序列，再对于第三个序列N，在这N*N的序列中进行二分搜，可以达O(N*log(N*N))=O(N*log(N))的时间。
而此题四个序列，若类似思路将三个序列相加的话将达N*N*N的空间，可能会超限，所以可以用两个N*N的序列，这样就问题时间O(N*N*logN),题目的N为4000，O(N^2*logN)还是可以在时限内的
#include <cstdio>
#include <cstdlib>
#include <algorithm>
using std::sort;
using std::binary_search;
using std::lower_bound;
using std::upper_bound;
int binsearchCount(int x,int *a,int N)
{
int count=0;
int *lwbd=a,*upbd=a+N;
if( binary_search(a,a+N,x) )
{
count+=upper_bound(a,a+N,x)-lower_bound(a,a+N,x);
}
return count;
}
int main(void)
{
int *a,*b,*c,*d;
int i,j,N,count,allN;
int *sab;
scanf("%d",&allN);
for(int idx=0;idx<allN;idx++)
{
scanf("%d",&N);
a=new int [N];
b=new int [N];
c=new int [N];
d=new int [N];
for(i=0;i<N;i++)
{
scanf("%d%d%d%d",&a[i],&b[i],&c[i],&d[i]);
}
sab=new int [N*N];
for(i=0;i<N;i++)
{
for(j=0;j<N;j++)
sab[i*N+j]=a[i]+b[j];
}
sort(sab,sab+N*N);
delete [] a;
delete [] b;
count=0;
for(i=0;i<N;i++)
{
for(j=0;j<N;j++)
{
count+=binsearchCount(-c[i]-d[j],sab,N*N);
}
}
delete [] c;
delete [] d;
if(idx>0)
printf("\n");
printf("%d\n",count);
delete [] sab;
}
return 0;
}