题目传送门
https://vjudge.net/problem/UVA-1152
题意
给你四个集合A，B，C，D，从四个集合中各取出一个数字加起来是0就符合条件，求出有多少组符合条件的组合。
分析
这题最直观的就是四重for循环枚举暴力了，可是这个复杂度几乎是难以接受的（虽然题目时间放的很宽），所以我们可以使用一些小技巧来简化一下。
比如我们可以两两先来两个for循环，把a+b(a属于A，b属于B)和c+d（c属于C，d属于D）枚举出来，这样我们就把问题简化成了两个数组相加为0的问题了。
如果这时候再去暴力枚举，有可能能过但是有点悬，那么我们还能怎么优化呢？这时候我们想到了，两个数相加为0，假设一个数为n那么另一个数肯定是要求-n了，那么我们完全可以对另一个数组进行排序，然后对其进行upper_bound()-lower_bound()（这是两个二分查找的函数，一个是找大于，一个是找大于等于，两者相减就是等于的个数，如果还不理解请自行查阅资料），这样我们就可以得到等于-n的数的个数了。所以我们就又把复杂度降低了。
刘汝佳在算法竞赛入门经典中建议了构造哈希表的算法，复杂度是O（n^2logn），这种二分我估算了一下复杂度也是o(n^2logn)，所以我干脆使用了简单明了的二分，如果对构造哈希表有兴趣的同学也可以自己试一下。
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
| #include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
typedef long long ll;
ll a[4000],b[4000],c[4000],d[4000];
vector<ll> add1,add2;
int main(){
int T;
while(cin>>T){
int n;
for(int k=0;k<T;k++){
if(k)
cout << endl;
add1.clear(),add2.clear();
cin>>n;
for(int i=0;i<n;i++)
cin>>a[i]>>b[i]>>c[i]>>d[i];
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
add1.push_back(a[i]+b[j]);
add2.push_back(c[i]+d[j]);
}
}
int sum=0;
sort(add2.begin(),add2.end());
for(int i=0;i<n*n;i++)
sum+=upper_bound(add2.begin(),add2.end(),-add1[i])-lower_bound(add2.begin(),add2.end(),-add1[i]);
cout << sum << endl;
}
}
return 0;
}
|