論一類平面點(diǎn)對(duì)曼哈頓距離問題.ppt

《論一類平面點(diǎn)對(duì)曼哈頓距離問題.ppt》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫。

1、一類平面點(diǎn)對(duì)曼哈頓距離問題的探究常州市第一中學(xué)陳子旸曼哈頓距離問題在信息學(xué)競賽題目中十分常見曼哈頓距離的定義：在歐幾里得空間的固定直角坐標(biāo)系上兩點(diǎn)所形成的線段對(duì)軸產(chǎn)生的投影的距離總和討論將圍繞一類平面上最大、最小曼哈頓距離點(diǎn)對(duì)問題展開目錄引例情況一：離線查詢、無修改情況二：在線查詢、修改情況三：在線查詢、無修改其他方法的討論總結(jié)引例(magic)題目大意：在一個(gè)ｋ(k<=7)維的空間中，有ｎ(n<=100000)個(gè)點(diǎn)，要求求出在這些點(diǎn)對(duì)中曼哈頓距離最遠(yuǎn)的點(diǎn)對(duì)之間的曼哈頓距離。例題分析直接暴力枚舉點(diǎn)對(duì)？顯然TLE！兩點(diǎn)間曼

2、哈頓距離的計(jì)算公式：以平面為例dist=

3、x1-x2

4、+

5、y1-y2

6、絕對(duì)值處理太麻煩！dist=

7、(x1-y1)-(x2-y2)

8、,(x1>x2&&y1>y2)

9、

10、(x1

11、(x1+y1)-(x2+y2)

12、,(x1>x2&&y1

13、

14、(x1y2)例題分析怎么處理？分類討論？？？？ＮＯ！??！完全不需要！

15、x

16、+

17、y

18、>=

19、x+y

20、也就是說：如果我們計(jì)算時(shí)如果不滿足條件，所計(jì)算出的值會(huì)比真實(shí)值小，不會(huì)更新答案！例題分析處理時(shí)，只需要分別統(tǒng)計(jì)

21、(x1+y1)-(x2+y2)

22、的最大值

23、和

24、(x1-y1)-(x2-y2)

25、的最大值，最后再取大的作答案就行了。高維推廣處理方法類似，以三維為例，只要統(tǒng)計(jì)x+y+z,x+y-z,x-y+z,x-y-z四類情況的答案就可以了。通過引例，我們初步了解了這類問題的特點(diǎn)，同時(shí)發(fā)現(xiàn)了解決這類問題的一個(gè)重要的思想：去絕對(duì)值在引例中，運(yùn)用了求最大值的條件和一個(gè)絕對(duì)值不等式，避免了分類討論。但實(shí)際運(yùn)用時(shí)往往要求最小值，我們不得不分類討論解決這類問題，接下來的部分按題目的不同要求分析了幾類不同情況。情況一：離線查詢，無修改例題2(DONUT)題目大意：在一個(gè)平面上有兩類點(diǎn)Ａ，Ｂ

26、。對(duì)于每個(gè)Ｂ類點(diǎn)求出離他曼哈頓距離最近的A類點(diǎn)與它的曼哈頓距離，其中Ａ類和Ｂ類點(diǎn)的個(gè)數(shù)都不超過50000個(gè)，點(diǎn)的坐標(biāo)范圍在長整數(shù)范圍內(nèi)。例題2分析能不能套用例題1（magic）的方法？dist=

27、(x1+y1)-(x2+y2)

28、,(x1>x2&&y1>y2)

29、

30、(x1

31、(x1-y1)-(x2-y2)

32、,(x1>x2&&y1

33、

34、(x1y2)糟糕！要求最小值

35、x

36、+

37、y

38、>=

39、x+y

40、例題2分析dist=

41、(x1+y1)-(x2+y2)

42、,(x1>x2&&y1>y2)

43、

44、(x1<

45、x2&&y1

46、(x1-y1)-(x2-y2)

47、,(x1>x2&&y1

48、

49、(x1y2)以分析在一個(gè)點(diǎn)左下的點(diǎn)為例例題2分析有點(diǎn)像二維RMQ問題？！樹套樹？二維ST？可以離線處理!例題2分析把所有點(diǎn)按照x的值排序，依次插入處理處理一個(gè)點(diǎn)時(shí)，所有插入的點(diǎn)的x的值都小于當(dāng)前點(diǎn)，所以只需要滿足y的條件就可以了處理對(duì)y的限制，只需要維護(hù)一棵維護(hù)x+y最大值的線段樹，能夠支持單點(diǎn)插入和區(qū)間查詢最值兩個(gè)操作就可以了情況二：在線查詢、帶修改例題3(DONUTEXT)在一個(gè)平面上給定一個(gè)點(diǎn)集，可以動(dòng)態(tài)地插入或

50、刪除點(diǎn)集中的點(diǎn)，并詢問離點(diǎn)集中某個(gè)點(diǎn)最近的點(diǎn)到該點(diǎn)的曼哈頓距離。點(diǎn)集的大小不超過100000。例題3分析在線，帶修改。離線算法神馬的不管用了……我們需要一個(gè)能同時(shí)處理兩個(gè)維度有序性的數(shù)據(jù)結(jié)構(gòu)有沒有想到區(qū)間第k大數(shù)問題？例題3分析在區(qū)間第k大數(shù)問題中，需要同時(shí)維護(hù)數(shù)在原序列中的位置和數(shù)的大小兩個(gè)序關(guān)系在區(qū)間第k大數(shù)問題中，可以使用歸并樹這一結(jié)構(gòu)下面來看一下如何把歸并樹運(yùn)用到本題中例題3分析把x的值作第一關(guān)鍵字（類比區(qū)間第k大數(shù)問題中數(shù)在原數(shù)組的位置），y的值作第二關(guān)鍵字（類比區(qū)間第k大數(shù)問題中數(shù)的值），建立歸并樹所有x符合

51、查詢要求的點(diǎn)分布在歸并樹中的O(log2n)個(gè)區(qū)間內(nèi)，在每個(gè)區(qū)間中，y有序，可以通過二分答案找到y(tǒng)符合要求的區(qū)間。最后，只要把歸并樹的每個(gè)節(jié)點(diǎn)用線段樹維護(hù)起來就可以了例題3分析123456781347256813472568134752681347256于是我們?cè)贠(nlog22n)的時(shí)間復(fù)雜度和O(nlog2n)的空間復(fù)雜度內(nèi)解決了這個(gè)問題情況三：在線查詢，無修改例題4(DONUTEXT2)題目大意：在一個(gè)平面上給定一個(gè)點(diǎn)集，查詢距離點(diǎn)（x，y）最近的點(diǎn)離它的曼哈頓距離，這里的x，y由上兩問的答案經(jīng)過某種變化得到。例題

52、4分析從題面分析，這題似乎比上一題目要簡單，因?yàn)闆]有修改操作若果直接套用上一題的做法，那這題就沒有存在的意義了所以一定有效率更高的算法！如何超越nlog22n?我們想到了求解區(qū)間第k大數(shù)的又一神器劃分樹例題4分析直觀地理解劃分樹，就是把快排的過程建成一棵樹1347526813427568123456781234567