POJ 2785 4 Values whose Sum is 0

Description

n行数据，每行4个，每列选出一个数加起来和为0，这样的情况共几种？

题目链接

二分

四个数分成两组，计算和，二分搜索

此题坑在于：跟前一组数据匹配的后一组数据可能不止一组！！！

Code

#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 4010;

int a[N], b[N], c[N], d[N], e[N * N], f[N * N];

int main()
{
    int n;
    while(~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)
            {
                e[i * n + j] = a[i] + b[j];
                f[i * n + j] = c[i] + d[j];///第二个j写成了i...
                int tem = i * n + j;
            }
        sort(e, e + n * n);
        sort(f, f + n * n);
        int ans = 0;
        for(int i = 0; i < n * n; ++i)
        {
            int pos = lower_bound(f, f + n * n, -e[i]) - f;
            while(pos != n * n && f[pos] == -e[i])//坑！
            {
                ans++;
                pos++;
            }
        }
        cout << ans << '\n';
    }
    return 0;
}

lower_bound and upperbound

lower_bound >= 找不到返回末元素的末地址（并不是末元素的首地址，一切都安排好了）

upper_bound >