鍵盤指揮官 的题解


记住在没有思路时使用题解,不要从它复制粘贴代码。请尊重题目和题解的作者。
在解题之前提交题解的代码会导致封禁。

作者: happylittle7

對於子題 \(1\) ,如果稍微觀察下,應該很容易發現棋盤上如果只有一個士兵,那士兵絕對有辦法到達棋盤上最左上方那一格且不會掉下去,故子題 \(1\) 只要全部輸出YES即可通過,輕鬆過得 \(10\) 分。

再來子題 \(2\) 和 \(3\) ,我們可以建立一個二維陣列模擬棋盤上的狀況,不難發現我們可以嘗試不斷將士兵全體向左或向上同時移動直到有士兵碰到最左上角那格,只要確保過程中沒有任何一次有士兵超出棋盤邊界,即可輸出YES,反之則輸出NO,在實作上,我們可以建立一個二維陣列維護棋盤上每位士兵的位置,這樣即可輸出答案了。時間複雜度的部分,假設最壞情況棋盤上只有一位士兵且位在最右下角,這樣我們就要整個棋盤向左移動 \(m\) 次,向上移動 \(n\) 次,故最終時間複雜度為 \(O(n^2m^2)\) (總共 \(n \times m\) 個格子,每個格子都向左移動 \(m\) 次和向上移動 \(n\) 次)。

不過這題如果再觀察一下的話,可以發現我們其實沒有必要維護所有士兵的位置,維護所有士兵位置並慢慢向左和向上移動非常沒有效率,實際上我們只在乎棋盤上最左邊和最上方士兵的座標,這樣就可以獲得更有效率的時間複雜度了,不過因為這次競賽題目有點多,所以就不特別強迫賽中做出這種最佳做法了,有興趣的人歡迎想想看。


评论

目前没有评论。