UVA 1152 --4 Values whose Sum is 0（枚举--中途相遇法）

「爱情、让人受尽委屈。」 2024-02-17 22:44 32阅读 0赞

### 4 Values whose Sum is 0 ###

Time Limit:9000MS Memory Limit:0KB 64bit IO Format:%lld & %llu

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 × B × C × D are such that a + b + c + d = 0. In the following, we  
assume that all lists have the same size n.

Input  
The input begins with a single positive integer on a line by itself indicating the number of the cases  
following, each of them as described below. This line is followed by a blank line, and there is also a  
blank line between two consecutive inputs.  
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 test case, your program has to write the number quadruplets whose sum is zero.  
The outputs of two consecutive cases will be separated by a blank line.

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

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

题意：大意是有四个集合A,B,C,D从每个中选择一个数，a,b,c,d,使得a+b+c+d = 0，问有多少不同的式子满足条件.

分析：如果数据量小， 直接四重循环即可解决问题，但是数据量太大！所以，考虑所有a+b的和，用一个数组保存所有的值，枚举 -(c+d），有多少和 a+b对应的。

用map会超时！

AC代码：

#include<cstdio>
    #include<cstring>
    #include<algorithm>
    using namespace std;
    const int maxn = 4000+5;
    int A[maxn],B[maxn],C[maxn],D[maxn];
    int a[maxn*maxn];
    
    int main(){
    	int T;
    	scanf("%d",&T);
    	int flag = 0;
    	while(T--){
    		if(flag++)printf("\n");
    		int n;
    		scanf("%d",&n);
    		for(int i = 0; i < n; i++){
    			scanf("%d%d%d%d",&A[i],&B[i],&C[i],&D[i]);
    		}
    		
    		for(int i = 0; i < n; i++){
    		  for(int j = 0; j < n; j++)
    		    a[i*n+j] = A[i] + B[j];
    		}
            
            sort(a,a+n*n);
    		int cnt = 0;
    				
    		for(int i = 0; i < n; i++){
    		  for(int j = 0; j < n; j++){
    		  	int tmp = C[i] + D[j];
    		  cnt+=upper_bound(a,a+n*n,-tmp) - lower_bound(a,a+n*n,-tmp);		  	
    		  }
    		}
    		
    		printf("%d\n",cnt);
    		
    	}
    	return 0;
    }

STL中的函数：

1、lower\_bound(a,a+n,value) //返回大于等于value值的第一个位置。

2、upper\_bound(a,a+n,value) //返回大于value值的最后一个值。

![Center][]

[Center]: https://image.dandelioncloud.cn/pgy_files/images/2024/01/29/2401efe2c1ee4592b4f4ec692a00f66e.png