Sacrament of the sum

来源POJ第2366题Sacrament of the sum

Description

— The Brother of mine, the Head of Monastic Order wants to know tomorrow about the results long-term researches. He wants to see neither more nor less than the Summering Machine! Even moreover, he wants our Machine — only a machine — to demonstrate its comprehension of the Sacrament of the Sum as deeply as it is possible. He wants our Machine to find two numbers that give the sum equal to the Sacred Number 10 000.
— Tsh-sh-sh! This is madness that borders on blasphemy! How can the Machine calculate the Sacred Number? Twenty seven years we work on it, but we’ve could teach it to tell if the sum of two introduced numbers greater or lower than 10 000. Can an ordinary mortal find two numbers that there sum will be equal to 10 000?
— But we’ll have to do it with the help of our Machine, even if it is not capable. Otherwise we’ll have… let’s say, big problems, if it is possible to call boiling oil like this. However, I have an idea. Do you remember, last week we’ve entered two numbers -7 and 13 into the Machine, and it answered that their sum is lower than 10 000. I don’t know how to check this, but nothing’s left for us than to believe to the fruit of our work. Let’s enter now a greater number than -7 and start up the Machine again. We’ll do like this again and again until we find a number that being added to 13 will give us 10 000. The only thing we are to do is to prepare an ascending list of numbers.
— I don’t believe in this… Let’s start with the sum that is obviously greater than the Sacred Number and we’ll decrease one of the summand. So we have more chances to avoid boilin… big problems.

Haven’t come to an agreement, the Brothers went away to their cells. By next day everyone of them has prepared a list of numbers that, to his opinion, could save them… Can both of the lists save them together?
Your program should decide, if it is possible to choose from two lists of integers such two numbers that their sum would be equal to 10 000.

Input

You are given both of these lists one by one. Format of each of these lists is as follows: in the first line of the list the quantity of numbers Ni of the i-th list is written. Further there is an i-th list of numbers each number in its line (Ni lines).The following conditions are satisfied: 1 <= Ni <= 50 000, each element of the lists lays in the range from -32768 to 32767. The first list is ascending and the second one is descending.

Output

You should write “YES” to the standard output if it is possible to choose from the two lists of integers such two numbers that their sum would be equal to 10 000. Otherwise you should write “NO”.

Sample Input

4
-175
19
19
10424
3
8951
-424
-788

Sample Output

YES

Hint

This problem has huge input data,use scanf() instead of cin to read data to avoid time limit exceed.

空间换时间

由题目可知数据大小再-32768到32768之间，因而可以直接利用大数组来存输入的数据，输入的输入如果大于0，放在第一个数组对应的A[in]位置，否则放在B[-in]，输入第二个数组的值时，先求出1000-in的值，如果大于0且A[10000-in]的值存在，说明找到了，或者B[in - 10000]存在，否则继续输入。

import java.util.*;

public class Main {
	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		boolean flag = false;
		int temp;
		int len1 = in.nextInt();
		int [] A = new int[65535];
		int [] B = new int[65535];
		for(int i = 0; i < len1; i++) {
			temp = in.nextInt();  //数组A升序
			if(temp >= 0)
				A[temp] = 1;
			else
				B[-temp] = 1;
		}
		int len2 = in.nextInt();
		if(len1 <= 0 || len2 <= 0){
			System.out.println("NO");
			return;
		}
		for(int i = 0 ; i < len2;i++) {
			temp = in.nextInt();  //数组B降序
			temp = 10000 - temp;
			if(temp >= 0 && A[temp] == 1){
				flag = true;
				break;
			}
			if(temp < 0 && B[-temp] == 1){
				flag = true;
				break;
			}
		}
		if(flag)
			System.out.println("YES");
		else
			System.out.println("NO");
	}
}

哈希Map

利用一个Map存放输入的值，和对应的数组标志，在数组B边输入时边查询即可。

import java.util.*;

public class Main {
		public static void main(String[] args) {
			Scanner in = new Scanner(System.in);
			boolean flag = false;
			int len1 = in.nextInt();
			int[] A = new int[len1];
			Map<Integer,Integer> map = new HashMap<Integer, Integer>();
			for (int i = 0; i < len1; i++) {
				A[i] = in.nextInt();  //数组A升序
				map.put(A[i],0);
			}
			int len2 = in.nextInt();
			int[] B = new int[65535];
			//Arrays.setAll(B,a -> -2147483647);
			if (len1 <= 0 || len2 <= 0) {
				System.out.println("NO");
				return;
			}
		for(int i = 0; i < len2 ; i++){
			int complement;
				B[i] = in.nextInt();
				//key = 1;
				complement = 10000 - B[i];
			if(map.containsKey(complement) && (map.get(complement) == 0)){
				flag = true;
				break;
			}
			map.put(B[i],1);
		}
			if (flag)
				System.out.println("YES");
			else
				System.out.println("NO");
		}
}

二分查找

思路同上，对输入数组B的每一个数在数组A里进行二分查找

import java.util.*;

public class Main {
	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		boolean flag = false;
		int len1 = in.nextInt();
		int [] A = new int[len1];
		for(int i = 0; i < len1; i++) {
			A[i] = in.nextInt();  //数组A升序
		}
		int len2 = in.nextInt();
		if(len1 <= 0 || len2 <= 0){
			System.out.println("NO");
			return;
		}
		int temp,left,right,mid,complement;
		for(int j = 0 ; j < len2 ; j++) {
			temp = in.nextInt();
			complement = 10000 - temp;
			//对数组a中的每个元素进行二分搜索
			left = 0;
			right = len1 - 1;
			while (left <= right) {
				mid = left + (right - left) / 2;
				if (complement == A[mid]) {
					flag = true;
					break;
				} else if (complement < A[mid]) {
					right = mid - 1;
				} else
					left = mid + 1;
			}
			if(flag)
				break;
		}
		if(flag)
			System.out.println("YES");
		else
			System.out.println("NO");
	}
}