POJ-2785 4 Values whose Sum is 0 题解

题目大意

给你四个数列A,B,C,D。从每个数列中各取出一个数，问有多少种方案使得4个数的和为0。
当一个数列中有多个相同的数字的时候，把它们当做不同的数对待。

解题思路

刚开始看到题目给了15s，想着$n^3$能过，结果$n^3$加二分还是T了。

想来想去不知道咋优化，后面发现可以先算出前两个数组的和和后两个数组的和再二分，之前还真没想过这种优化。。

还是做题不够啊。

完整代码

#include <iostream>
#include <algorithm>
using namespace std;

typedef long long ll;
ll a[4050], b[4050], c[4050], d[4050];
ll sum1[4050 * 4050], sum2[4050 * 4050];

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	int n; cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
		cin >> b[i];
		cin >> c[i];
		cin >> d[i];
	}
	int cnt = 1;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++)	sum1[cnt] = a[i] + b[j], sum2[cnt++] = c[i] + d[j];
	}
	ll ans = 0;
	sort(sum2 + 1, sum2 + cnt);
	for (int i = 1; i < cnt; i++) {
		ll sum = sum1[i];
		int t;
		t = upper_bound(sum2 + 1, sum2 + cnt, sum * -1) - lower_bound(sum2 + 1, sum2 + cnt, sum * -1);
		ans += t;
		//cout << a[i] << "    " << b[j] << "    " << c[k] << "    " <<sum<<"    "<< d[pos] << endl;
	}
	cout << ans << endl;
}