By Leo_璇哥

更新日期:

文章目录

4 Values whose Sum is 0

Time Limit: 15000MS Memory Limit: 228000K

Total Submissions: 4991 Accepted: 1171

Case Time Limit: 5000MS

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

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

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

Sample Input
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
5

Hint
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).

Source
Southwestern Europe 2005

这道题如果直接背包的话最坏情况仍然是O(n^4)的,所以必须想办法把复杂度降下来.
分为左右两半分别枚举,则显然各枚举两列的话复杂度会降得最多.
考虑先把左半边的情况全存下来,然后查找右半边每个和的负数在左边的个数.
如果直接枚举查找,则复杂度仍然为O(n^4).
所以可以先把左边的结果排序,然后对右面的每对和做二分查找其负值.
这样的话,复杂度为O(n^2 log n),符合本题要求

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
#include<stdio.h>  
#include<stdlib.h>  
  
#define MAXN 4001  
  
int apb[MAXN*MAXN],cpd[MAXN*MAXN];  
int a[MAXN],b[MAXN],c[MAXN],d[MAXN];  
  
int cmp(const void *a,const void *b)  
{  
    return (*(int *)a - *(int *)b);  
}  
  
int bin_search(int * a, int key,int n);  
  
int main()  
{  
    int n,i,j,ans,t;  
  
    while(~scanf("%d",&n))  
    {  
        for( i = 0;i<n;++i)  
            scanf("%d%d%d%d",&a[i],&b[i],&c[i],&d[i]);  
        for(i = 0;i < n;++i )  
            for(j = 0;j < n;++j )  
            {  
                apb[i*n+j] = a[i] + b[j];  
                cpd[i*n+j] = c[i] + d[j];  
            }  
              
            qsort(apb,n*n,sizeof(int),cmp);  
  
            t=n*n;  
            for(ans = i = 0 ; i<t;++i)  
                ans += bin_search(apb,-cpd[i],t);  
  
            printf("%d\n",ans);  
    }  
  
    system("pause");  
    return 0;  
}  
  
int bin_search(int *a,int key,int n)  
{  
    int cnt,up,low,mid,t;  
    cnt = 0;  
    up = n-1;  
    low = 0;  
    while(low<=up)  
    {  
        mid = (up + low)>>1;  
        if(key == a[mid])  
            break;  
        if(key < a[mid])  
            up = mid - 1;  
        else  
            low = mid + 1;  
    }  
    if(key == a[mid])  
    {  
        ++cnt;  
        t = mid;  
        while(t>0 && key == a[--t])  
            ++cnt;  
        while (mid < n-1 && key == a[++mid])   
            ++cnt;  
    }  
    return cnt;  
}
文章目录