当前位置:编程学习 > C/C++ >>

4 Values whose Sum is 0

这个题目同上道二分的题目一样,只是把数字分成两堆,在排序用二分的思想,但是必须明白,不是在找到一个的条件的情况下跳出,可能只有重复的。这里是重点。继续我的二分之路,我的时间复杂度很高,效率不怎么好。看了下别人的代码,好像都是用hash,下一站就是hash了。

4 Values whose Sum is 0

Time Limit: 15000MS   Memory Limit: 228000K
Total Submissions: 11586   Accepted: 3249
Case Time Limit: 5000MS

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 228 ) 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

5
 
代码:
[cpp] 
<span style="font-family:FangSong_GB2312;font-size:18px;">#include<iostream> 
#include<cmath> 
#include<vector> 
#include<algorithm> 
#define maxn 4004 
using namespace std; 
int map1[maxn*maxn]; 
int map2[maxn*maxn]; 
int a[maxn],b[maxn],c[maxn],d[maxn]; 
int main() 

      int n,i,j,k,sum,p; 
      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++) 
         map1[i*n+j]=a[i]+b[j]; 
      for(i=0;i<n;i++) 
        for(j=0;j<n;j++) 
          map2[i*n+j]=c[i]+d[j]; 
      sort(map1,map1+n*n); 
      sort(map2,map2+n*n); 
      sum=0; 
      p=n*n-1; 
      for(i=0;i<n*n;i++) 
      {  
        while(p>=0&&map1[i]+map2[p]>0) p--; 
        if(p<0) break; 
        int temp=p; 
        while(temp>=0&&map1[i]+map2[temp]==0) 
        { 
            sum++; temp--; 
        } 
      } 
      printf("%d\n",sum); 
      //system("pause"); 
       return 0; 

          
</span> 

补充:软件开发 , C++ ,
CopyRight © 2022 站长资源库 编程知识问答 zzzyk.com All Rights Reserved
部分文章来自网络,