【POJ 2785】【折半枚举】4 Values whose Sum is 0【暑期 No.6】

题意：

        给定各有n个整数的四个数列A、B、C、D。要从每个数列中各取出1个数，使四个数的和为0。求出这样的组合的个数。当一个数列中有多个相同的数字时，把它们作为不同的数字看待。

 

分析：

        如果直接对四个数列进行枚举的话，将是O(n^4)的复杂度，因此可以考虑折半枚举的思想。

        将A、B数组相加的所有可能性列出来加入数组，O(n^2)，再进行排序，O(n^2 logn)，再对C、D数组相加的所有可能性进行枚举，O(n^2)，再对枚举出的每一个值在第一个排序过的数组中进行二分搜索，O(logn)。大大降低了时间复杂度，这种思想需要学习。

 

代码：

#include <cstdio>
#include <iostream>
#include <algorithm> 
#define rep(i,a,b) for(int i = a;i <= b;i++)
using namespace std;
const int SIZE = 4010;

int a[5][SIZE];
int ans1[SIZE*SIZE],ans2[SIZE*SIZE];
int n,num1,num2;

int main()
{
	while(~scanf("%d",&n))
	{
		rep(i,1,n)
			scanf("%d%d%d%d",&a[1][i],&a[2][i],&a[3][i],&a[4][i]);
		num1 = 0;
		rep(i,1,n)
			rep(j,1,n)
				ans1[++num1] = a[1][i]+a[2][j];
		num2 = 0;
		rep(i,1,n)
			rep(j,1,n)
				ans2[++num2] = a[3][i]+a[4][j];
		int cnt = 0;
		sort(ans2+1,ans2+1+num2);
		rep(i,1,num1){
			int x = (-1)*ans1[i];
			cnt += upper_bound(ans2+1,ans2+1+num2,x)-lower_bound(ans2+1,ans2+1+num2,x);
			//巧妙运用lower_bound和upper_bound可以实现所有需要的二分形式
			//并且更加准确
			//需要充分掌握
			//因为如果数据中出现大量的相同元素，单纯的二分便不再适用，使用现有的函数更加高效 
		}
		printf("%d\n",cnt);
	}	
	return 0;
}