poj 2785 让和为0 暴力&二分

题目链接：http://poj.org/problem?id=2785

大意是输入一个n行四列的矩阵，每一列取一个数，就是四个数，求有多少种着四个数相加和为0的情况

首先脑海里想到的第一思维必然是一个个枚举，用四个for循环，那时间复杂度变成了On4，n的最大值是4000.

肯定会超时。那么，为了简化时间，首先我们可以开两个至少4000*4000的数组分别把第一列与第二列的和的情况

，第三列与第四列的和的情况存起来。这样就只用考虑两个数组的情况。

然后把两个数组排序，一个数组从头部开始同时另一个数组从尾部开始讨论和为0的情况(利用了递增性质和递减性质)

 #include<cstdio>

 #include<algorithm>

 using namespace std;

 int a[],b[],c[],d[];

 int ab[*+],cd[*+];

 int main()

 {

     int n,i,j,k,num,sum,x;

     while (~scanf("%d",&n))

     {

         for (i=;i<n;i++)

             scanf("%d %d %d %d",&a[i],&b[i],&c[i],&d[i]);

         k=;

         for (i=;i<n;i++){

             for (j=;j<n;j++)

                ab[k++]=a[i]+b[j];

         }

         k=;

         for (i=;i<n;i++){

             for (j=;j<n;j++)

                cd[k++]=c[i]+d[j];

         }

         sort(ab,ab+n*n);

         sort(cd,cd+n*n);

         x=n*n-;sum=;

         for (i=;i<n*n;i++)

         {

             while (x>=&&ab[i]+cd[x]>)

                 x--;

             if (x<)

                 break;

             num=x;

             while (ab[i]+cd[num]==&&num>=)

             {

                 sum++;

                 num--;

             }

         }

         printf("%d\n",sum);

     }

     return ;

 }

二分也很简单,找到相等个数就行

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 using namespace std;

 int a[],b[],c[],d[];

 int ab[*+],cd[*+];

 int k2;

 int check(int x)

 {

     int left=,right=k2-,mid;

     while (left<=right)

     {

         mid=(left+right)/;

         if (x==cd[mid])

         {

             int w=,e=mid;

             while (x==cd[e]&&e<k2)

                 e++,w++;

             e=mid-;

             while (x==cd[e]&&e>)

                 e--,w++;

             return w;

         }

         else if (x<cd[mid])

             right=mid-;

         else

             left=mid+;

     }

     return ;

 }

 int main()

 {

     int t,i,j,q;

     while (~scanf("%d",&t))

     {

         for (i=;i<=t;i++)

             scanf("%d %d %d %d",&a[i],&b[i],&c[i],&d[i]);

         memset(ab,,sizeof(ab));

         memset(cd,,sizeof(cd));

         int k1=,sum=;

         k2=;

         for (i=;i<=t;i++)

         {

             for (j=;j<=t;j++)

             {

                 ab[k1++]=a[i]+b[j];

                 cd[k2++]=-(c[i]+d[j]);

             }

         }

         sort(cd+,cd+k2);

         for (i=;i<k1;i++)

             sum+=check(ab[i]);

         printf("%d\n",sum);

     }

     return ;

 }