题目

题目描述：
SUM问题可以表示为：给定四个具有整数值的列表A，B，C，D。
计算多少个四元组（a，b，c，d）∈A x B x C x D使得a + b + c + d = 0。在下文中，我们假定所有列表的大小均相同。

输入描述：
输入文件的第一行包含列表n的大小（该值可以最大为4000）。然后，我们有n行包含四个分别属于A，B，C和D的整数值（绝对值最大为2 28）。

输出描述：
对于每个输入文件，您的程序必须使四个数的总和为零。

解析

1）知识点

  • 这道题是一道简单二分，但是思路就很重要。

2）看题目

  • 找到题目就是说从四组数里面，每组选出一个，要问相加等于0的有几种。

3）算法分析

  1. 分析过这道题之后你最暴力的想法应该就是开一个四重循环把四组数据遍历一遍。但是题目不可能允许的。
  2. 然后你可能有高级一点的想法：先得到前三列，然后对第四列进行一个二分查找。这样会快那么一点点，但题目也不可能允许。
  3. 不过上面的二分已经讲到点子上了，我们既然可以二分一组就可以二分两组。但是两组我们要特殊操作一下。
  4. 我们上面不是有四个数相加吗，我们可以看成是两个数加两个数，然后就可以将两个数的所有组合放到一个数组里面。
  5. 再判断另外两个数的组合时，对上面的两个组合进行二分查找。这样就快了很多了。

4）算法操作

  1. 我上面简简单单说了要进行二分查找，现在我们就来看一下操作：
  2. 首先是合并两列数据： 
    for (int i = 1; i <= n; i++)
    for (int j = 1; j <= n; j++)
        v.push_back(a[i] + b[j]);
  3. 然后就是取值二分查找： 
    ll ans = 0;
for (int i = 1; i <= n; i++)
    for (int j = 1; j <= n; j++) {
        int x = -(c[i] + d[j]);
        ans += upper_bound(v.begin(), v.end(), x) - lower_bound(v.begin(), v.end(), x);
    }

5）打代码

  1. 首先输入四组数据。
  2. 然后合并两组。
  3. 再对这两组进行二分搜索。
  4. 下面全代码~

AC代码 

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
typedef long long ll;
#define IOS ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
//代码预处理区

const int MAX = 1e6 + 7;
int a[MAX], b[MAX], c[MAX], d[MAX];
vector<int> v;
//全局变量区

//函数预定义区

int main() {
    IOS;
    int n; cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> a[i] >> b[i] >> c[i] >> d[i];
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            v.push_back(a[i] + b[j]);
    sort(v.begin(), v.end());
    ll ans = 0;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++) {
            int x = -(c[i] + d[j]);
            ans += upper_bound(v.begin(), v.end(), x) - lower_bound(v.begin(), v.end(), x);
        }
    cout << ans << endl;
    return 0;
}
//函数区