题目描述

ZJM 有四个数列 A,B,C,D，每个数列都有 n 个数字。ZJM 从每个数列中各取出一个数，他想知道有多少种方案使得 4 个数的和为 0。当一个数列中有多个相同的数字的时候，把它们当做不同的数对待。请你帮帮他吧！

输入描述

第一行：n（代表数列中数字的个数） （1≤n≤4000）
接下来的 n 行中，第 i 行有四个数字，分别表示数列 A,B,C,D 中的第 i 个数字（数字不超过 2 的 28 次方

输出描述

输出不同组合的个数。

输入样例

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

输出样例

5

思路分析

1、采用四重循环遍历四个数组的方法复杂度O（$N^4$)，无法接受
2、采用分而治之的思想。分别枚举AB和CD。

• 枚举A+B的和
• 对A+B的和排序
• 枚举C+D、计算它的相反数在A+B中出现多少次，计算的方法为二分查找相反数在A+B中第一次出现的位置和最后一次出现的位置

代码

#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
int n;
vector<int> a,b,c,d,ab,cd;
//返回第一个等于x的位置 
int findl(int x){int l=0,r=ab.size()-1,ans=-1;while(l<=r){int mid=(l+r)/2;if(ab[mid]==x){ans=mid;r=mid-1;}else if(ab[mid]>x) r=mid-1;else l=mid+1;}return ans;
}
//返回最后一个等于x的位置 
int findr(int x){int l=0,r=ab.size()-1,ans=-1;while(l<=r){int mid=(l+r)/2;if(ab[mid]==x){ans=mid;l=mid+1;}else if(ab[mid]>x) r=mid-1;else l=mid+1;}return ans;
}int main(){cin>>n;int ans=0; for(int i=0;i<n;i++){int t1,t2,t3,t4;cin>>t1>>t2>>t3>>t4;a.push_back(t1);b.push_back(t2);c.push_back(t3);d.push_back(t4);}//计算a+b; for(int i=0;i<n;i++){for(int j=0;j<n;j++){ab.push_back(a[i]+b[j]);}}sort(ab.begin(),ab.end());//枚举c+dfor(int i=0;i<n;i++){for(int j=0;j<n;j++){int temp=(c[i]+d[j])*-1;//寻找第一次出现的位置、最后一次出现的位置 int l=findl(temp),r=findr(temp);if(l!=-1){ans+=(r-l+1);}}}cout<<ans<<endl; 
}