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

时间：2022-05-31 19:37:04

题意：

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

分析：

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

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

 #include <cstdio>

 #include <algorithm>

 using namespace std;

 const int maxn =  + ;

 int A[maxn], B[maxn], C[maxn], D[maxn], sum[maxn*maxn], cnt;

 int main()

 {

     //freopen("in.txt", "r", stdin);

     int T;

     scanf("%d", &T);

     while(T--)

     {

         int n;

         scanf("%d", &n);

         for(int i = ; i < n; ++i) scanf("%d%d%d%d", &A[i], &B[i], &C[i], &D[i]);

         cnt = ;

         for(int i = ; i < n; ++i)

             for(int j = ; j < n; ++j)

                 sum[cnt++] = A[i] + B[j];

         sort(sum, sum + cnt);

         long long ans = ;

         for(int i = ; i < n; ++i)

             for(int j = ; j < n; ++j)

                 ans += upper_bound(sum, sum + cnt, -C[i]-D[j]) - lower_bound(sum, sum + cnt, -C[i]-D[j]);

         printf("%lld\n", ans);

         if(T) puts("");

     }

     return ;

 }

代码君

相关文章