b684. 4. 狗狗遊戲 -- 2015高雄市資訊學科能力競賽高中組 | From: [163.32.57.178] | 發表日期 : 2023-05-10 15:37

隨機產生了一個數列為例子：

9

4 8 7 5 6 2 3 1 9

 

i + 1 在 i 的右邊嗎：

1 2 3 4 5 6 7 8 9

0 1 0 1 1 0 0 1 0

 

i + 1 在 i 的左邊嗎：

1 2 3 4 5 6 7 8 9

1 0 1 0 0 1 1 0 0

 

一開始必然往右走，走到 1 勢必不用折返。

剩下的每一個數字，可以根據「現在是不是正在往右/左走」和「接下來要去的數字是不是在現在這個數字的左/右邊」來判斷抵達時需不需要折返。

E.g. 現在正在 1，且正在往右走。如果 2 在 1 的右邊，就不需要折返，可以直接抵達 2；但如果 2 不在 1 的右邊，那就需要折返，而且會變成往左走。

 

走到這個數字需要折返嗎：

1 2 3 4 5 6 7 8 9

0 1 1 1 1 0 1 0 1

 

總共 6 個數字要折返，所以答案是 6。

判斷 i+1 是不是在 i 的左邊/右邊只需要將整個數列看過一次即可（不是在左邊就是在右邊，所以只需要一個陣列），而依序判斷每一個數字是不是需要折返才能抵達也只需要將 1 到 N-1 的數字依序看過一次就可以，因此也是 O(N) 的作法。

（但還是跑了 0.2s，不知道如何加速Q）