[Java] UVa 11063 B2-Sequence

題目連結

題意:
給定一組遞增序列，將其任兩數相加之和不可重複(包含自己與自己相加)

如1, 2, 4, 8
任兩數相加有: 1+1, 1+2, 1+4, 1+8, 2+2, 2+4, 2+8, 4+4, 4+8, 8+8

其中測資元素大小不超過10000

解法:
當下看到第一個直覺是用一個陣列存總和列表，要放新的前先檢查有無重複
但因為是任兩數相加都要比，數字一多搜尋重複所耗費時間也很可觀

後來發現可以改良陣列，用陣列index當作總和
因為數字上限10000，任兩數之和不會超過20000
設立布林陣列，預設false，相加判斷index
為true表示已出現過，就不是B2-Sequence
切記換下一組測資前要重設陣列

程式(Java):

	import java.util.*;
	class Main{
	public static void main(String args[]){
	Scanner input = new Scanner(System.in);
	int times = 1;
	while (input.hasNext()){
	boolean flag = false; //true = not B2
	int A = input.nextInt(); //How many numbers
	int B[] = new int[A];
	boolean Sum[] = new boolean[20001]; //兩數的上限都是10000
	int current = 0;
	for (int i = 0; i < A; i++){
	B[i] = input.nextInt();
	if (B[i] <= current || B[i] < 1) //not positive or increasing
	flag = true;
	current = B[i];
	}
	if (!flag){
	for (int i = 0; !flag && i < A; i++)
	for (int j = i; !flag && j < A; j++){
	int add = B[i] + B[j];
	if (!Sum[add])
	Sum[add] = true;
	else
	flag = true;
	}
	}
	if (flag)
	System.out.println("Case #" + times + ": It is not a B2-Sequence.");
	else
	System.out.println("Case #" + times + ": It is a B2-Sequence.");
	times++;
	System.out.println();
	}
	}
	}

view raw UVa11063.java hosted with ❤ by GitHub