poj 2785 4 Values whose Sum is 0

你的名字 2022-06-16 10:57 75阅读 0赞

4 Values whose Sum is 0

<table> 
 <tbody> 
  <tr> 
   <td><strong>Time Limit:</strong>&nbsp;15000MS</td> 
   <td>&nbsp;</td> 
   <td><strong>Memory Limit:</strong>&nbsp;228000K</td> 
  </tr> 
  <tr> 
   <td><strong>Total Submissions:</strong>&nbsp;21828</td> 
   <td>&nbsp;</td> 
   <td><strong>Accepted:</strong>&nbsp;6600</td> 
  </tr> 
  <tr> 
   <td align="center" colspan="3" style="color:rgb(14,173,0)"><strong>Case Time Limit:</strong>&nbsp;5000MS</td> 
  </tr> 
 </tbody> 
</table>

Description

The SUM problem can be formulated as follows: given four lists A, B, C, D of integer values, compute how many quadruplet (a, b, c, d ) ∈ A x B x C x D are such that a + b + c + d = 0 . In the following, we assume that all lists have the same size n .

Input

The first line of the input file contains the size of the lists n (this value can be as large as 4000). We then have n lines containing four integer values (with absolute value as large as 2 28 ) that belong respectively to A, B, C and D .

Output

For each input file, your program has to write the number quadruplets whose sum is zero.

Sample 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

Sample Output

Hint

Sample 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).

题目大意：

这个题目非常好理解，就是在每一列中取出一个数，相加和为0，得到坐标，问一共有多少种方法。

题目解析：

这是一个非常简单的枚举，用暴力就可以解决，但是可能会超时，我用的是暴力加二分的方法，首先将前两个数相加，再将后两个数

相加，再用二分搜索的方法去找到两个相反数即可。

代码：

#include<iostream>
    #include<cstring>
    #include<algorithm>
    #define maxn 4005
    using namespace std;
    int a[maxn],b[maxn],c[maxn],d[maxn];
    int ab[maxn*maxn+1],cd[maxn*maxn+1];
    int k2;
    int fun(int x)
    {
        int left=1,right=k2-1,mid;
        while (left<=right)
        {
            mid=(left+right)/2;
            if (x==cd[mid])
            {
                int w=0,temp=mid;
                while (x==cd[temp]&&temp<k2)
                    temp++,w++;
                temp=mid-1;
                while (x==cd[temp]&&temp>0)
                    temp--,w++;
                return w;
            }
            else if (x<cd[mid])
                right=mid-1;
            else
                left=mid+1;
        }
        return 0;
    }
    int main()
    {
        int t,i,j,q;
        while (cin>>t)
        {
            for (i=1;i<=t;i++)
                cin>>a[i]>>b[i]>>c[i]>>d[i];
            memset(ab,0,sizeof(ab));
            memset(cd,0,sizeof(cd));
            int k1=1,sum=0;
            k2=1;
            for (i=1;i<=t;i++)
            {
                for (j=1;j<=t;j++)
                {
                    ab[k1++]=a[i]+b[j];
                    cd[k2++]=-(c[i]+d[j]);
                }
            }
            sort(cd+1,cd+k2);
            for (i=1;i<k1;i++)
                sum+=fun(ab[i]);
            cout<<sum<<endl;
        }
        return 0;
    }