前陣子，我的小徒弟去報名他人生第一次的 APCS 考試，可以說是他學習電腦科學以來第一次的正式上機考試．一共有四題的程式設計題目，前面兩題算是簡單的，第三題算中等，第四題比第三題再進階一點點．這篇文章就來談談第三題的解題思考．
完整的題目在 https://zerojudge.tw/ShowProblem?problemid=f607 ，首先，要解題之前，請先確定自已己經百分百了解題目．這一個題目的解決過程可以分成下列 2 個部份,
1. 讀取輸入參數，因為輸入參數並非按照切割次序而輸入的，我們要進行切割時是按照次序來切割的．因此，我們必須對輸入參數做處理，以讓沒有次序的參數集合變成有次序的參數集合．
2. 每一次切割時，都需要知道左右兩端的長度，這樣才能算出該次切割的費用，而知道左右兩端的長度，這需要一個快速的行為才能符合題目的要求．因為題目提到切割次數最多會到二十萬次，並且棍子的長度可以到 10 7 那麼長.
有關讀取輸入參數的內容，基本上有兩種做法，可以把切割資料全部讀進來之後，再以切割次序做排序．若是這樣做，這個動作將花費 O (n lg n) ，假設是用 quick sort. 除此以外，我們可以換個角度思考，題目給的切割次序不會出錯，也就是說當切割資料讀進來時，切割次序就是一種 key，不會重覆，因為第 n 次切割只會發生一次．所以可以用 (key, value) 的 hash table 來存放切割資料．由於 hash table 的 set , get 都是 O(1) ，所以這讀取動作將花費 O(n)．
因此，第一個部份的時間複雜度最小可以到 O(n).
接下來，第二部份是計算每一次切割的費用．可以想像正在發生第 k 次的切割，也就是我們要想一個快速的方法讓我們可以查到在第 k 次切割時，當時所在的位置往左邊和往右邊走碰到的第一個切割點. 假設一開始用一個 boolean array 來代表被切割的點，
index : 0 1 2 3 4 5 ......98 99 100 101 102 103 ........ n
value: f f f f f t ..... t f f f t f ....... f
一開始 array 的都是 false ，被切割過的點就變成 true，假設第 k 次的點要切割在第 100 個位置，而 98 和 102 是 true，所以這一次的切割費用是 102 - 98 = 4．如果以程式的角度來看的話，你得寫一個 for loop 從 100 往右邊走，找到第一個 true ，然後再往左邊走找到第一個 true，然後再做減法．這樣的尋找方式是 O(n)，而這個會發生在切割資料的迴圈裡，假設切割資料是 m 筆，因此這一段的時間複雜度是 O(nm)，一旦 n 和 m 都很大時，這就相當於是 O(n*n)．而 n 最大的值會到 20 萬，因此 O(n*n) 是不能接受的．因此，用 array 做搜尋是不合格的，所以我們必須用其他的資料結構，並且這個資料結構所花費的成本要小於 O(n) (比 array 一個一個找再快).
這時候，答案其實已很明顯了，能夠比 array O(n) 還要快的只有 binary search tree O(lg n) 或是 hash table O(1) ．在這一個動作的過程中，我們需要能 "往左走" 和 "往右走" ，Hash table 顯然不會是個好選擇，因為 hash table 無法儲存元素之間的 "順序"，因此，就剩下 binary search tree 了．binary search tree 在儲存的過程花費 O(lg n) 時間，而尋找的過程也是花費 O(lg n) 時間，而且 binary search tree 的特性讓我們可以 "往左走" "往右走" 來找到最近被切割過的位置．因此，採用 binary search tree 之後，時間複雜度可變成 O (m lg n) ，如果 m 和 n 都很大時，就是 O( n lg n)，這個比剛剛的 O(n*n) 快上很多.
最後，以下的程式碼是我的小學徒提供的，在很大的測試資料下仍花費了 0.25 秒完成，雖然不是最快，但也符合了題目 2 秒內的要求.
0 意見:
張貼留言