四数之和为零 [UVA – 1152] 简析

四数之和为零 [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;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注