Posted on 2010-10-15 11:15
MiYu 閱讀(2063)
評論(0) 編輯 收藏 引用 所屬分類:
ACM_資料
Matrix67原創 Trackback: http://www.matrix67.com/blog/archives/108
如果說今年這時候OIBH問得最多的問題是二分圖，那么去年這時候問得最多的算是離散化了。對于“什么是離散化”，搜索帖子你會發現有各種說法，比如“排序后處理”、“對坐標的近似處理”等等。哪個是對的呢？哪個都對。關鍵在于，這需要一些例子和不少的講解才能完全解釋清楚。
離散化是程序設計中一個非常常用的技巧，它可以有效的降低時間復雜度。其基本思想就是在眾多可能的情況中“只考慮我需要用的值”。下面我將用三個例子說明，如何運用離散化改進一個低效的，甚至根本不可能實現的算法。
《算法藝術與信息學競賽》中的計算幾何部分，黃亮舉了一個經典的例子，我認為很適合用來介紹離散化思想。這個問題是UVA10173(http://acm.uva.es/p/v101/10173.html)，題目意思很簡單，給定平面上n個點的坐標，求能夠覆蓋所有這些點的最小矩形面積。這個問題難就難在，這個矩形可以傾斜放置（邊不必平行于坐標軸）。
這里的傾斜放置很不好處理，因為我們不知道這個矩形最終會傾斜多少度。假設我們知道這個矩形的傾角是α，那么答案就很簡單了：矩形面積最小時四條邊一定都挨著某個點。也就是說，四條邊的斜率已經都知道了的話，只需要讓這些邊從外面不斷逼近這個點集直到碰到了某個點。你不必知道這個具體應該怎么實現，只需要理解這可以通過某種方法計算出來，畢竟我們的重點在下面的過程。
我們的算法很顯然了：枚舉矩形的傾角，對于每一個傾角，我們都能計算出最小的矩形面積，最后取一個最小值。
這個算法是否是正確的呢？我們不能說它是否正確，因為它根本不可能實現。矩形的傾角是一個實數，它有無數種可能，你永遠不可能枚舉每一種情況。我們說，矩形的傾角是一個“連續的”變量，它是我們無法枚舉這個傾角的根本原因。我們需要一種方法，把這個“連續的”變量變成一個一個的值，變成一個“離散的”變量。這個過程也就是所謂的離散化。
我們可以證明，最小面積的矩形不但要求四條邊上都有一個點，而且還要求至少一條邊上有兩個或兩個以上的點。試想，如果每條邊上都只有一個點，則我們總可以把這個矩形旋轉一點使得這個矩形變“松”，從而有余地得到更小的矩形。于是我們發現，矩形的某條邊的斜率必然與某兩點的連線相同。如果我們計算出了所有過兩點的直線的傾角，那么α的取值只有可能是這些傾角或它減去90度后的角（直線按“\”方向傾斜時）這么C(n,2)種。我們說，這個“傾角”已經被我們 “離散化”了。雖然這個算法仍然有優化的余地，但此時我們已經達到了本文開頭所說的目的。
對于某些坐標雖然已經是整數（已經是離散的了）但范圍極大的問題，我們也可以用離散化的思想縮小這個規模。最近搞模擬賽Vijos似乎火了一把，我就拿兩道Vijos的題開刀。
VOJ1056(http://www.vijos.cn/Problem_Show.asp?id=1056) 永遠是離散化的經典問題。大意是給定平面上的n個矩形（坐標為整數，矩形與矩形之間可能有重疊的部分），求其覆蓋的總面積。平常的想法就是開一個與二維坐標規模相當的二維Boolean數組模擬矩形的“覆蓋”（把矩形所在的位置填上True）。可惜這個想法在這里有些問題，因為這個題目中坐標范圍相當大（坐標范圍為-10^8到10^8之間的整數）。但我們發現，矩形的數量n<=100遠遠小于坐標范圍。每個矩形會在橫縱坐標上各“使用”兩個值， 100個矩形的坐標也不過用了-10^8到10^8之間的200個值。也就是說，實際有用的值其實只有這么幾個。這些值將作為新的坐標值重新劃分整個平面，省去中間的若干坐標值沒有影響。我們可以將坐標范圍“離散化”到1到200之間的數，于是一個200*200的二維數組就足夠了。實現方法正如本文開頭所說的“排序后處理”。對橫坐標（或縱坐標）進行一次排序并映射為1到2n的整數，同時記錄新坐標的每兩個相鄰坐標之間在離散化前實際的距離是多少。這道題同樣有優化的余地。
最后簡單講一下計算幾何以外的一個運用實例（實質仍然是坐標的離散）。才考的VOJ1238(http://www.vijos.cn/Problem_Show.asp?id=1238)中，標程開了一個與時間范圍一樣大的數組來儲存時間段的位置。這種方法在空間上來看十分危險。一旦時間取值范圍再大一點，盲目的空間開銷將導致Memory Limit Exceeded。我們完全可以采用離散化避免這種情況。我們對所有給出的時間坐標進行一次排序，然后同樣用時間段的開始點和結束點來計算每個時刻的游戲數，只是一次性加的經驗值數將乘以排序后這兩個相鄰時間點的實際差。這樣，一個1..n的數組就足夠了。
離散化的應用相當廣泛，以后你會看到還有很多其它的用途。
2007.04.05補充：
VOJ1056那個例子看來還是有人不明白。
我發一張示意圖，注意左邊的10*7的數組是如何等價地轉化為右邊兩個4*4的數組的
