题目的意思很明确，ABCD四个集合，，从各个集合中抽取一个数，求将四个数相加等于0的组合数。
由于N最大达到4000，所以，暴力的方法过不了，就是时间限制为15000MS也是不行。
不过我们可以双向搜索，也就是折半搜索。
先求出CD这两个集合的两两配对的新的集合CD，然后在从CD集合中找AB集合两两配对的和k的负数有多少个。用upper_bound和lower_bound函数可以很快的求解出来。
简单来说，a+b+c+d=0，先算出c + d，a + b = -（c + d），在集合CD中查找。
下面的是AC的代码：
#include <iostream>#include <algorithm>#include <cstdio>using namespace std;int n;int A[4005], B[4005], C[4005], D[4005];int CD[4005 * 4005];void solve(){int i, j, k;for(i = 0; i < n; i++)for(j = 0; j < n; j++)CD[i * n + j] = C[i] + D[j];//求集合CDsort(CD, CD + n * n);//排序__int64 ans = 0;for(i = 0; i < n; i++){for(j = 0; j < n; j++){k = A[i] + B[j];ans += upper_bound(CD, CD + n * n, -k) – lower_bound(CD, CD + n * n, -k); //查找有多少个元素是等于 -k的}}printf("%I64d\n", ans);}int main(){int i;scanf("%d", &n);for(i = 0; i < n; i++){scanf("%d", &A[i]);scanf("%d", &B[i]);scanf("%d", &C[i]);scanf("%d", &D[i]);}solve();return 0;}
版权声明：本文为博主原创文章，未经博主允许不得转载。
其实，每个人都是幸福的。只是，你的幸福，常常在别人眼里。
