#教學教學文(五) 離散化 | 程式設計板

嗨嗨大家好！我消失好久了@@ 這次要講的主題是離散化老問題為什麼要學離散化呢？這一次就留到文章中再講吧那麼開始囉~ 首先要來說說離散化是什麼離散化就是把一個數列從數值改成它在這群數字中的大小排名例如7122 87 933703 235就會變成3 1 4 2 離散化有一個特性就是它會保留數值之間的大小關係但是詳細差多少從離散化之後的數據是無法得知的那離散化的目的是什麼呢？第一種情況如果數值之間的差距多少不重要只有排名(或是大小關係)對解題有幫助的時候就會做離散化第二種情況使程式要跑的東西變少例如說某一題的值域範圍到10^9 但是實際上只需要處理100個東西那就可以不用從0跑到10^9 只要跑那100個東西所在的位置就行了例如今年TOI入營考的pD就屬於這種情況 N=3000，值域範圍C=10^6 如果以所有可能的點的位置去跑O(C^2)的話是10^12 但是其實可以經過一些預處理之後就可以用O(N^2)的時間複雜度解決了！ (聽說這題有N log N的做法不過我不會QQ) 接著就是離散化的做法啦 (之前有人已經提到過不過漏了一點點小東西哦) 離散化的實作分為三步驟 1.sort 2.unique + resize 3.lower_bound unique可以讓連續多個相同的值變為一個而sort之後相同的值會被放在一起所以unique的時候就會讓所有種類的數值都只剩下一個並且由小到大排好啦但unique不會改變陣列或容器的大小因此使用vector的resize來把vector的大小調整成數值種類的個數最後就用lower_bound(vector.begin(), vector.end(), x)來找到原始數值排在vector的第幾個也就是第幾小的啦 (小補充如果已知數值不會重複的話就可以不用unique哦只要sort就可以了！因為數值不重複的話就不會有連續多個相同的數值因此做unique是不會有任何用處的然後在寫這個小補充的同時我意識到我昨天寫的一份code是不需要unique的QQ) (想要詳細了解unique可以看這裡： http://www.cplusplus.com/reference/algorithm/unique/ ) 好啦又到了我們的code時間啦這是只做離散化的code (也就是把數值變排名) Code： http://codepad.org/CkF8DDgR 然後啊 Codeforces的915E是離散化+線段樹有興趣的人可以去做做看哦！這次的教學文就到這裡了有問題都歡迎提出來討論然後如果我文章中有可以改進的地方也麻煩跟我說一下哦！下一篇：我試著寫寫看尤拉迴路如果不行的話我再想想@@ (當然是希望可以啦)