二分搜尋+upper_bound,lower_bound

原文連結：http://www.spoj.com/problems/SUMFOUR/

題意：有四個數列A，B，C，D。 每個數列n個數，在每個數列中都任意取出一個數。要求這四個數相加等于0，問這樣的四個數組合共有多少組？

Input:
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
Output:
5      

解法：hash或者二分搜尋

二分答案：

#include <bits/stdc++.h>
using namespace std;
const int maxn=2600;
int n,a[maxn],b[maxn],c[maxn],d[maxn],cd[maxn*maxn];
int main()
{
    int n;
    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)
    {
        cd[i*n+j]=c[i]+d[j];
    }
    sort(cd,cd+n*n);
    int res=0;
    for(int i=0;i<n;++i){
        for(int j=0;j<n;++j)
        {
            int k=-(a[i]+b[j]);
            res+=upper_bound(cd,cd+n*n,k)-lower_bound(cd,cd+n*n,k);
        }

    }
    cout<<res<<endl;

    return 0;
}
           

題意：有四個數列A，B，C，D。 每個數列n個數，在每個數列中都任意取出一個數。要求這四個數相加等于0，問這樣的四個數組合共有多少組？