折半枚举：四数之和为零

题目描述

给定各有N个整数的四个数列A 、B、C、D。要从每个数列中各取1个数。使四个数的和为0。求这样的组合的个数。当一个数列中有多个相同的数字时，把它们作为不同的数字看待。

输入

第一行：每个数列包含的整数个数 N
接下来N行：每行包含四个各自属于数列A、B、C、D的数字

输出

第一行：使四个数和为0的组合个数

样例输入

6
-45   22  42   -16 
-41  -27  56    30
-36   53  -37   77
-36   30  -75  -4626  -38  -10   62
-32  -54  -6    45

样例输出

5

提示

说明：(-45, -27, 42, 30), (26, 30, -10, -46), (-32, 22, 56, -46),(-32, 30, -75, 77), (-32, -54, 56, 30) 这5个组合和为0。
对于100%的数据,1 <= n <= 4000,|(数字的值)| <= 1,000,000,000

思路分析

直接枚举，时间复杂度为，在n≤4000的情况下行不通。

可以折半枚举，数组AB存储所有A[i]+B[j]的和，数组CD存储所有C[i]+D[j]的和。

数组AB与数组CD均按升序排序，便于后续二分查找。

题中明确表示，相同数字作为不同数字看待，遍历数组AB时可以压缩连续相同数字，在数组CD中用二分查找高效计算连续相同数字个数。

代码

#include<bits/stdc++.h>
#define ll long long
using namespace std;
int n,ans;
int main(){ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);cin>>n;vector<int>a(n),b(n),c(n),d(n);for(int i=0;i<n;i++){cin>>a[i]>>b[i]>>c[i]>>d[i];}vector<int>ab,cd;for(int i=0;i<n;i++){for(int j=0;j<n;j++){ab.push_back(a[i]+b[j]);cd.push_back(c[i]+d[j]);}}sort(ab.begin(),ab.end());sort(cd.begin(),cd.end());int i=0,total=n*n;while(i<total){int x=ab[i],cnt_ab=0;while(i<total&&ab[i]==x){i++;cnt_ab++;}int target=0-x;auto it=lower_bound(cd.begin(),cd.end(),target);auto im=upper_bound(cd.begin(),cd.end(),target);int cnt_cd=im-it;ans+=cnt_ab*cnt_cd;}cout<<ans;return 0;
}

（用long long会内存超限）