在給定的範圍內比給定數目

Question

我們給出N（N < = 10 ）上的2D平面和整數d點（N < = 10 ），我們希望更大的查找最小元素找到兩個點p1，p2（在p1右邊的p2），使得p1.y和p2.y之間的差值至少爲D並且p2.x - p1.x被最小化。

的x和y軸是範圍0..10

這是從過去USACO競賽一個problem。

這裏是我的嘗試來解決它：
MAXY = N點中的最大y軸。
假設我們知道p1，那麼我們可以很容易地找到p2;通過將y軸在p1.y+D範圍內的所有點取爲MAXY或取值範圍爲0到p1.y-D，並取x軸最小的點大於p.x。這將是p2的最佳選擇。

但是，由於我們不知道P1，我們將不得不嘗試P1的所有點，因此找到P2的最佳選擇應該是有效的。

我爲此使用了細分樹。樹中的每個節點將按x軸的排序順序存儲相應範圍內的所有點。在查詢時，如果一個節點落在查詢範圍內，那麼我們在數組上進行二進制搜索以獲得p1.x，並返回大於它的最小元素。

對於p1的每一次選擇，我們用範圍0，p1.y-D和p1.y + D，MAXY查詢樹兩次，並取回返兩點中的最好值。

樹的建築可以在O（NlogN）時間完成。 每個查詢將花費O（logN * logN）時間，並且我們進行N次查詢，因此總時間爲（Nlogn * logn），可能無法在2秒的時間限制內運行。 （10 * 20 * 20）。 此外內存採取將是O（NlogN），這是約80 MB（100000 * 20 * 4 kb）這是太多，因爲極限是64 MB。

我們如何更快地查詢查詢並使用較小的空間？

Answer 1

它可以做得更容易。

假設您有兩個數組副本：一個按Y軸排序，另一個按X軸排序。現在，您將遍歷Y排序數組和每個點（讓它命名爲cur），您應該在X排序數組中搜索適當的點（使用最小的p2.x - p1.x）。在二進制搜索的情況下會找到相同的點或Y座標小於cur + D的點，您應該從X排序的數組中刪除該點（我們再也不需要X排序數組中的那個點，因爲我們只是增加Y座標）並再次運行二進制搜索。答案將是二進制搜索結果中最小的。

由於我們需要快速計時，因此我們應該快速擦除陣列中的點。它可以通過使用二叉樹來完成 - 它可以在O（logN）時間內擦除任何節點，並且可以在O（logN）時間內進行二分搜索。由於您只從樹中刪除每個節點一次，並且需要O（logN + logN）時間 - 總時間將爲O（N * logN）。預處理時間也是O（N * logN）。此外，所採用的內存將是O（N）。

順便說一句，你的解決方案也是適當的，因爲實際N是10^5而不是10^6。這可以讓您的解決方案保持時間低於2秒，並使用少於20MB的內存。

Answer 2

怎麼樣只是做排序&掃描。

按x排序，因爲您想通過x找到最小差異。它需要O（N logN）時間並且到位。

從x的頭部維護兩個索引i和j。

速度越快先找到位置| P [i] .y - P [j] .y | > D

和X = | P [i] .x - P [j] .x |是您第一個可用的選擇。

然後通過向前移動到索引來更新X.嘗試P [i + 1]，從P [i + 2]掃描爲P [j]並增加至| P [i] .x - P [j] .x | > = X.如果有一個可用的新X，將其設置爲X.

這可能會使起初做很多比較。但是，由於你更新X，不知何故會使你的比較範圍縮小。