POJ-3441:4 Values whose Sum is 0--多元素之和判定

原题传送门

题目大意

解题思路

首先应该想到的是，四重for循环，遍历A,B,C,D中的每一个元素，判断它们的和是否为0。但是$O(n^4)$O(n4)显然是过不了的。

考虑

优化1

将$a+b+c+d=0$a+b+c+d=0转化为$a+b=-c-d$a+b=−c−d，分别遍历$A,B$A,B和$C,D$C,D数组，枚举每一个$a+b$a+b记为数组$AB$AB,$-c-d$−c−d记为数组$CD$CD。此举复杂度$O(n^2)$O(n2)，遍历$AB$AB数组的每个元素。判断他在$CD$CD数组中是否有相等元素，以及相等元素的个数，因为题中是将相同元素看做不同值，因此很可能有多个值相等，在这里WA了好几次

优化2

查找$AB$AB数组在$CD$CD数组中有几个相等值的问题，可以使用二分搜索，直接使用STL大法

upper_bound(cd, cd + n * n, ab[i]) - lower_bound(cd, cd + n * n, ab[i])

上面就是$ab[i]$ab[i]元素在$CD$CD数组中相等元素的个数

完整代码

#include<iostream>
#include<iomanip>
#include<cmath>
#include<string.h>
#include<queue>
#include<vector>
#include<map>
#include<algorithm>
using namespace std;

#define Max 2501
#define ll long long
#define inf 1000005
#define p pair<ll,ll>

ll a[Max], b[Max], c[Max], d[Max];
ll ab[Max*Max], cd[Max*Max], ans = 0;
ll n = 0;
int main() {
	cin >> n;
	for (ll i = 0; i < n; i++) cin >> a[i] >> b[i] >> c[i] >> d[i];
	for (ll i = 0; i < n; i++) {
		for (ll j = 0; j < n; j++) {
			ab[i*n + j] = a[i] + b[j];
			cd[i*n + j] = -c[i] - d[j];
		}
	}
	sort(cd, cd + n * n); sort(ab, ab + n * n);
	for (ll i = 0; i < n*n; i++) {
		//有个坑，同样的数字的话多统计多次，所以
		ans += upper_bound(cd, cd + n * n, ab[i]) - lower_bound(cd, cd + n * n, ab[i]);
	}
	cout << ans << endl;
}