最近修了 edx 上的這門課：Data Structures and Algorithm Design Part I 数据结构与算法设计(上)
是由北京清華大學所開設的課程
邊修邊記一下心得
第一章主要在講一些基礎
像是時間複雜度的算法，遞迴、迴圈、DP（動態規劃）還有D&C
舉的實例是 LCS，最長共同子序列
比較有趣的是作業，一共有三題
第一題給你 n 個點（一維）以及區間 [a,b] 以及 m 次查詢，求落在區間內的點的數目
0 ≤ n, m ≤ 5×10^5
0 <= a,b <= 10^7
滿喜歡清華的 judge system 有分數制，可以先求有再求好
寫一個最直接的解法，複雜度是 O(mn)，可以過一半的測資拿 50 分
要再精進就是先 sort 然後做二分搜，降到O(mlogn)
這題有兩個點要注意，第一個是我二分搜寫完以後居然還是超時...
結果是因為我用了cin跟cout，改成scanf跟printf就過了
輸出入果然還是佔了大多數時間...
第二個點是這題的二分搜不太一樣
以前寫過的都是「找出某個數」，但這題你要寫的是「找出<=某個數」
所以在程式碼上要改一下，不然會找不到；改錯的話可能會找錯或是無窮迴圈
第二題叫做 zuma，就是那個吐珠子的遊戲
給你一個初始序列，假設是 ABCDB 好了
再給你 n 個操作，每一個都是插入一顆珠子到某個 index
求每個操作結束之後的序列長怎樣
我後來上網搜尋這題相關資料的時候，才發現好像是要用雙向 linked list
但我那時候根本沒想到這個東西，只當成是一般模擬題
就用 string 做了，一樣 AC
第三題是大魔王
題目包裝的很漂亮！我很喜歡這題，要特地記錄一下
海上有很多燈塔，每個燈塔都對應到一個二維座標(x,y)；燈塔的探照燈會照自己的右上角跟左下角
求有多少對燈塔可以互相照到
互相照到的數學定義其實就是一對燈塔(x1, y1) 跟 (x2, y2) 滿足 x2>x1 && y2>y2
會說這題包裝的很漂亮，是因為假設你把燈塔按照 x 排序以後
答案其實就是「順序數對」的總數，也就是全部數目減掉逆序數對
例如說 1 4 5 3 2
逆序數對是：(4,3), (4,2), (5,3), (5,2), (3,4)
順序數對是：(1,4), (1,5), (1,3), (1,2), (4,5)
因為這數對有先對 x 排序，所以順序數對很顯然就是題目所求的燈塔對的數目
這經典算法的解法是 merge sort 的最後一個步驟
在這邊稍微講一下
例如到合併時，左半邊是：7 4 2；右半邊是：8 3 1（由大到小排）
當你第一個數拿右半邊的8的時候，就知道左半的 3 個數（7, 4, 2）一定都比8小
以此類推，就可以算出到底有多少組「順序數對」
要求逆序數對的話其實也差不多啦，稍微改一下而已
這題之所以是大魔王是因為，做完之後還是只拿到 95 分
上完搜了一下，要拿滿分好像要搭配輸入優化
我懶得做了，所以就算了...
