×
解除綁定,重新設定系統帳號的密碼
您的系統帳號 ID:
您的系統帳號:
您的帳號暱稱:
設定新密碼:
設定新密碼:
×
請輸入要加入的「課程代碼」
請向開設課程的使用者索取「課程代碼」
分類題庫
解題動態
排行榜
討論區
競賽區
登入
註冊
發表新討論
#35124: 折返次數
kaeteyaruyo@gmail.com
(kinoe_T)
學校 : 國立成功大學
編號 : 81196
×
傳送站內訊息
傳給:
主題:
內容:
來源 : [140.113.136.221]
最後登入時間 :
2024-01-31 16:39:28
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)
ZeroJudge Forum