[Java] UVa 10730 Antiarithmetic?

題目連結

題意:
每行測資給定一個permutation (即 0, 1, . . . , n − 1元素的一種排列)，判斷其中是否包含任3個數形成等差數列，若否，稱為 antiarithmetic permutation，輸出yes；若存在，輸出no

例如:
4 5 0 3 1 2
其中的 4 3 2 是等差數列，所以要輸出 no

解法:
一開始我用暴力解，每次找到等差前、中項後
都會一一走訪到數列尾以找後項，果不其然TLE了
包含透過Arraylist 的 indexOf 方法

時間複雜度可能落在 O(N^3)...
(Worst case 前中後項)

後來只好爬文
看到網路上大多是在讀取數列的同時記錄位置
因為permutation就是該數列恰包含 0 ~ n-1 的元素

我們只要倒過來
用陣列的 index 表示真正的數值
陣列存的值則為原本數列的位置所在

以 4 5 0 3 1 2 為例

陣列第 4 格擺 0, 第 5 格擺 1, 第 0 格擺 2, 依此類推

從陣列裡，我們可以知道
數值 0 在原數列 2 的位置
數值 1 在原數列 4 的位置
...

而3元素的等差數列的定義為:  前項, 前項+公差, 前項+2*公差
也就是我們只要依次判斷
arr[0], arr[1], arr[2] (公差1)
arr[0], arr[2], arr[4] (公差2)
arr[1], arr[2], arr[3] (公差1)
arr[1], arr[3], arr[5] (公差2)
...
存的值是不是遞增(也就是在原本數列也是照順序出現)
或是遞減(公差為負的情況)
像這個例子，arr[0], arr[1], arr[2]遞增，所以輸出 no

大概評估一下，時間複雜度應該在O(N^2)以下
(前項N，公差從1枚舉到 後項到數列長度前)

程式(Java):

	import java.util.*;
	public class Main {
	public static void main(String args[]) {
	Scanner sc = new Scanner(System.in);
	while (sc.hasNextLine()) {
	String s[] = sc.nextLine().split(" ");
	if (s[0].length() == 1)
	break;
	int num = Integer.parseInt(s[0].substring(0, s[0].indexOf(':')));
	int arr[] = new int[num];
	for (int i = 1; i <= num; i++)
	arr[Integer.valueOf(s[i])] = i-1;
	boolean anti = true;
	for (int i = 0; i < arr.length && anti; i++)
	for (int j = 1; i + 2 * j < arr.length && anti; j++) {
	if (arr[i] < arr[i + j] && arr[i + j] < arr[i + 2 * j])
	anti = false;
	if (arr[i] > arr[i + j] && arr[i + j] > arr[i + 2 * j])
	anti = false;
	}
	if (anti)
	System.out.println("yes");
	else
	System.out.println("no");
	}
	}
	}

view raw UVa10730.java hosted with ❤ by GitHub