首页 > 搜索 > BFS搜索 > POJ 2785 4 Values whose Sum is 0 [解题报告] Java
2013
11-12

POJ 2785 4 Values whose Sum is 0 [解题报告] Java

4 Values whose Sum is 0

问题描述 :

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 .

输入:

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 .

输出:

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

样例输入:

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

样例输出:

5

温馨提示:

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

解题代码:

//* @author: [email protected]
import java.io.*;
import java.util.*;
public class Main
{
 public static void main(String[] args) throws IOException
 {
	InputStreamReader is=new InputStreamReader(System.in);
	BufferedReader in=new BufferedReader(is);
	String s=in.readLine();
	int a=Integer.parseInt(s);
	int[] t1=new int[a];
	int[] t2=new int[a];
	int[] t3=new int[a];
	int[] t4=new int[a];
	int[] t5=new int[a*a];
	int[] t6=new int[a*a];
	int abl=0,cdl=0;
	String[] ss;
	for(int i=0;i< a;i++)
	{
         ss=in.readLine().split(" ");
	  t1[i]=Integer.parseInt(ss[0]);
	  t2[i]=Integer.parseInt(ss[1]);
	  t3[i]=Integer.parseInt(ss[2]);
	  t4[i]=Integer.parseInt(ss[3]);
	}
	for(int i=0;i< a;i++)
	  for(int j=0;j< a;j++)
	  {
	   t5[abl++]=t1[i]+t2[j];
	   t6[cdl++]=t3[i]+t4[j];
	  }
	Arrays.sort(t5);
	Arrays.sort(t6);
	int l1=0,l2=cdl-1,ans=0,k,m;
	while(l1< abl&&l2>-1)
	{
	  if(t5[l1]+t6[l2]==0){
		k=0;
		m=0;
		for(int i=l1;i< abl;i++)
	         if(t5[l1]!=t5[i]) break;
		  else k++;
		l1+=k;
		for(int i=l2;i>-1;i--)
		  if(t6[l2]!=t6[i]) break;
		  else m++;
		l2-=m;
		ans+=k*m;
	  }
	  else if(t5[l1]+t6[l2]>0) l2--;
	  else l1++;
      }
      System.out.println(ans);
  }
}

  1. 第二种想法,我想来好久,为啥需要一个newhead,发现是把最后一个节点一直返回到嘴上面这层函数。厉害,这道题之前没样子想过。