UVa 1152 (中途相遇法) 4 Values whose Sum is 0

题意：

要从四个数组中各选一个数，使得这四个数之和为0，求合法的方案数。

分析：

首先枚举A+B所有可能的值，排序。

然后枚举所有-C-D的值在其中用二分法查找。

 1 #include <cstdio>
 2 #include <algorithm>
 3 using namespace std;
 4 
 5 const int maxn = 4000 + 10;
 6 int A[maxn], B[maxn], C[maxn], D[maxn], sum[maxn*maxn], cnt;
 7 
 8 int main()
 9 {
10     //freopen("in.txt", "r", stdin);
11 
12     int T;
13     scanf("%d", &T);
14     while(T--)
15     {
16         int n;
17         scanf("%d", &n);
18         for(int i = 0; i < n; ++i) scanf("%d%d%d%d", &A[i], &B[i], &C[i], &D[i]);
19         cnt = 0;
20         for(int i = 0; i < n; ++i)
21             for(int j = 0; j < n; ++j)
22                 sum[cnt++] = A[i] + B[j];
23         sort(sum, sum + cnt);
24         long long ans = 0;
25         for(int i = 0; i < n; ++i)
26             for(int j = 0; j < n; ++j)
27                 ans += upper_bound(sum, sum + cnt, -C[i]-D[j]) - lower_bound(sum, sum + cnt, -C[i]-D[j]);
28         printf("%lld
", ans);
29         if(T) puts("");
30     }
31 
32     return 0;
33 }

代码君