POJ – 2785 4 Values whose Sum is 0 (二分)

给你四个数列A,B,C,D。从每个数列中各取出一个数，使4个数的和为0.
当一个数列中有多个相同的数字的时候，把它们当做不同的数对待

Input第一行：n（代表数列中数字的个数） （1≤n≤4000）
第二行：依次输入A,B,C,D（输入一个A再输入一个B）

Output输出不同组合的个数。

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

Sample Output5
HintSample Explanation: Indeed, the sum of the five following quadruplets is zero: (-45, -27, 42, 30), (26, 30, -10, -46), (-32, 22, 56, -46),(-32, 30, -75, 77), (-32, -54, 56, 30).

理解：
对于二分的题目我们很容易想到一般的解决方法 对于这道题 如果使用暴力枚举的话复杂度将会到达N的四次方 虽然数据规模不大 但一定是不可以的 所以我们可以换个思路想问题我们可以把前两个数组和后两个数组分别看做一个数组 然后前两个数组任意两个相加 得到一个 两个数组和 的数组 后两个一样 然后进行二分查找 如果为零总数加一

注意：
这道题里面需要注意的一个点是有可能出现相加后的数有可能有相同的且和后面相加为零 这种情况我们需要考虑 代码中用一个while来考虑这种情况
还有 我们其实只需要对后面那个数组进行排序就可以了

以下是AC代码：

#include <algorithm>
#include <stdio.h>
#include <cstring>
using namespace std;
int a[4005],b[4005],c[4005],d[4005];
int suma[16000005];
int sumb[16000005];
int n,flag=0;
int main()
{
    int i,j,ans=0,start,mid,end;
    while(~scanf("%d",&n))
    {
    for(i=0;i<n;i++)
        scanf("%d %d %d %d",&a[i],&b[i],&c[i],&d[i]);
    for(i=0;i<n;i++)
    {
        for(j=0;j<n;j++)
        {
            suma[flag]=a[i]+b[j];
            sumb[flag]=c[i]+d[j];
            flag++;
        }
    }
    sort(sumb,sumb+flag);
    for(i=0;i<=flag-1;i++)
    {
        start=0;
        end=flag-1;
        while(end-start>0)       //
        {
            mid=(start+end)>>1;
            if(suma[i]+sumb[mid]>=0)
            end=mid;
            else
            start=mid+1;        //
        }
        while(suma[i]+sumb[start]==0 && start<flag) //防止在第二个数组内有相同的数与suma[i]相加等于零 
        {
            ans++;
            start++;            //
         } 
    }
    printf("%d\n",ans);
    }
    return 0; 
 } 

对于这道题 其实想强调的还是二分的边界条件 很容易弄错