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 2 28 ) 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).
题目意思:有四列数,从每一列中选一个数使4个数之和为0;一个有几种情况;
解题思路:先将4列变成2堆数,再用二分快速查找:
1 #include <iostream>
2 #include <algorithm>
3
4 using namespace std;
5 const int MAX = 4000 + 300;
6 const int MAX1 = 4000*4000 + 300;
7 int N,ti,TTT;
8 int a[4][MAX];
9 int sum1[MAX1];
10 int sum2[MAX1];
11
12 void twofe(int x)
13 {
14 //cout<<x<<" x "<<endl;
15 x = - x;
16 int tou = 0;
17 int wei = ti;
18
19 while(tou <= wei)
20 {
21 int temp =( tou + wei )/2;
22
23 if(x < sum2[temp])
24 {
25 wei = temp - 1;
26 }
27 else if ( x > sum2[temp])
28 {
29 tou = temp + 1;
30 }
31 else if( x == sum2[temp])
32 {
33 // cout<<sum2[temp]<<" temp "<<endl;
34 TTT++;
35 for(int i = temp -1;i>=0;i--)
36 if(sum2[i]==x)
37 TTT++;
38 else
39 break;
40 for(int i = temp +1;i < ti;i++)
41 if(sum2[i]==x)
42 TTT++;
43 else
44 break;
45 return;
46 }
47 }
48
49
50 }
51
52 int main()
53 {
54
55 cin>>N;
56 for(int i = 0;i < N;i++)
57 {
58 for(int j= 0;j < 4;j++)
59 cin>>a[j][i];
60 }
61
62 ti = 0;
63 TTT = 0;
64 for(int i = 0;i<N;i++)
65 for(int j = 0;j<N;j++)
66 {
67 sum1[ti] = a[0][i] + a[1][j];
68 sum2[ti++] = a[2][i] + a[3][j];
69 }
70 sort(sum2,sum2+ti);
71 // for(int i = 0;i < ti;i++)
72 // cout<<sum2[i]<<' ';
73 //cout<<endl;
74
75
76 for(int i = 0;i < ti;i++)
77 {
78 twofe(sum1[i]);
79 }
80
81 cout<<TTT<<endl;
82
83
84 return 0;
85 }