高效算法——J 中途相遇法，求和

---恢复内容开始---

J - 中途相遇法

Time Limit:9000MS Memory Limit:0KB 64bit IO Format:%lld & %llu

Description

The SUM problem can be formulated as follows: given four lists A, B, C, D<tex2html_verbatim_mark> of integer values, compute how many quadruplet (a, b, c, d ) AxBxCxD<tex2html_verbatim_mark> are such that a + b + c + d = 0<tex2html_verbatim_mark> . In the following, we assume that all lists have the same size n<tex2html_verbatim_mark> .

Input

The input begins with a single positive integer on a line by itself indicating the number of the cases following, each of them as described below. This line is followed by a blank line, and there is also a blank line between two consecutive inputs.

The first line of the input file contains the size of the lists n<tex2html_verbatim_mark> (this value can be as large as 4000). We then have n<tex2html_verbatim_mark> lines containing four integer values (with absolute value as large as 2²⁸<tex2html_verbatim_mark> ) that belong respectively to A, B, C<tex2html_verbatim_mark> and D<tex2html_verbatim_mark> .

Output

For each test case, the output must follow the description below. The outputs of two consecutive cases will be separated by a blank line.

For each input file, your program has to write the number quadruplets whose sum is zero.

Sample Input

1

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

Sample Output

Sample Explanation: Indeed, the sum of the five following quadruplets is zero: (-45, -27, 42, 30), (26, 30, -10, -46), (-32, 22, 56, -46),(-32, 30, -75, 77), (-32, -54, 56, 30).

题目思路：

大意：每列找一个数，得到和为0的序列，有几种不同的方案

分析：

如果进行四重循环，毫无疑问会超时，这时需要用到枚举案例，

对1，2列的数求一个和，3,4列的数求一个和，然后进行二分查找

程序代码：

#include<cstdio>
#include<algorithm>
using namespace std;
int a[16000010];
int b[16000010];
int p[4010][4];
int t;
int erfen(int x)
{
    int cnt=0;
    int l=0,r=t-1,mid;
    while(r>l)
    {
        mid=(l+r)>>1;
        if(b[mid]>=x) r=mid;
        else l=mid+1;
    }

    while(b[l]==x&&l<t)
    {
        cnt++;
        l++;
    }
    return cnt;
}
int main()
{
    int n,i,j,T;
    long long res;
    scanf("%d",&T);
    while(T--)
    {
       
        scanf("%d",&n);
        res=0;
        for(i=0;i<n;i++)
            for(j=0;j<4;j++)
                scanf("%d",&p[i][j]);
        t=0;
        for(i=0;i<n;i++)
            for(j=0;j<n;j++)
                a[t++]=p[i][0]+p[j][1];
        sort(a,a+t);
        t=0;
        for(i=0;i<n;i++)
            for(j=0;j<n;j++)
                b[t++]=p[i][2]+p[j][3];
        sort(b,b+t);
        for(i=0;i<t;i++)
            res+=erfen(-a[i]);
        printf("%d
",res);
         if(T) printf("
");
        }
    return 0;
}

View Code

---恢复内容结束---