首页 > 代码库 > UVa1152 4 Values whose Sum is 0 (中途相遇法)

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

链接:http://vjudge.net/problem/36014

分析:先枚举a和b,把所有a+b记录下来放在一个有序数组中,然后枚举c和d,查一查-c-d有多少种方法写成a+b的形式(二分查找)。

 1 #include <cstdio> 2 #include <algorithm> 3 using namespace std; 4  5 const int maxn = 4000 + 5; 6  7 int a[maxn], b[maxn], c[maxn], d[maxn]; 8 int ab[maxn * maxn], cd[maxn * maxn]; 9 10 int main() {11     int T;12     scanf("%d", &T);13     while (T--) {14         int n;15         scanf("%d", &n);16         for (int i = 0; i < n; i++) scanf("%d%d%d%d", &a[i], &b[i], &c[i], &d[i]);17         for (int i = 0; i < n; i++)18             for (int j = 0; j < n; j++) ab[i * n + j] = a[i] + b[j];19         for (int i = 0; i < n; i++)20             for (int j = 0; j < n; j++) cd[i * n + j] = -(c[i] + d[j]);21         sort(cd, cd + n * n);22         long long ans = 0;23         for (int i = 0; i < n * n; i++)24             ans += upper_bound(cd, cd + n * n, ab[i]) - lower_bound(cd, cd + n * n, ab[i]);25         printf("%lld\n", ans);26         if(T) printf("\n");27     }28     return 0;29 }

 

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