5

2D 平面上のN (N <= 10 6 ) 点と整数 D (N <= 10 6 ) が与えられた場合、2 つの点 p1,p2 (p1 の右側にある p2) を見つけて、p1.yでp2.yあり、少なくとも D であり、p2.x - p1.x最小化されます。

x 軸と y 軸の範囲は 0..10 6

これはUSACO の過去のコンテストの問題です。

ここにそれを解決するための私の試みがあります:
MAXY = N ポイント間の最大 y 軸。
p1 を知っていると仮定すると、p2 は非常に簡単に見つけることができます。p1.y+Dy 軸がMAXY から MAXY までの範囲または 0 から までの範囲にあるすべてのポイントをp1.y-D取得し、最小の x 軸が より大きいポイントを取得しますp.x。これは、p2 に最適な選択です。

しかし、p1 がわからないので、p1 のすべてのポイントを試す必要があるため、p2 の最適な選択を効率的に見つける必要があります。

そのためにセグメントツリーを使用しました。ツリー内のすべてのノードは、対応する範囲内のすべてのポイントを x 軸のソート順に格納します。クエリ中に、ノードがクエリ範囲内にある場合、配列でバイナリ検索を行い、p1.xそれよりも大きい最小の要素を返します。

p1 を選択するたびに、範囲 0,p1.yD と p1.y+D,MAXY を使用してツリーを 2 回クエリし、返された 2 つのポイントの中で最も良いものを取得します。

ツリーの構築は O(NlogN) 時間で実行できます。すべてのクエリには O(logN*logN) 時間がかかり、N 個のクエリを作成するため、合計所要時間は (Nlogn*logn) であり、2 秒の時間制限内で実行されない可能性があります。(10 6 *20*20)。また、使用されるメモリは O(NlogN) になり、これは約 80 mb (100000*20*4 kb) であり、制限が 64 mb であるため多すぎます。

クエリをより速く、より少ないスペースで実行するにはどうすればよいでしょうか?

4

2 に答える 2

5

それははるかに簡単に行うことができます。

配列の 2 つのコピーがあるとします。1 つは Y 軸で並べ替えられ、もう 1 つは X 軸で並べ替えられます。ここで、Y ソートされた配列を反復処理し、各ポイント (cur と名付けます) について、X ソートされた配列内の適切なポイント (最小の p2.x - p1.x) をバイナリ検索する必要があります。二分探索の場合、同じ点または Y 座標が cur+D より小さい点が見つかる場合は、X ソート配列からその点を削除するだけです (X ソート配列でその点が再び必要になることはありません。 Y 座標を増やして)、二分探索を再度実行します。答えは、二分探索結果の最小のものになります。

速いタイミングが必要なため、配列からポイントをすばやく消去する必要があります。これは、バイナリ ツリーを使用して実行できます。O(logN) 時間で任意のノードを消去し、O(logN) 時間でバイナリ検索を実行できます。ツリーから各ノードを 1 回だけ削除すると、O(logN + logN) 時間かかるため、合計時間は O(N * logN) になります。前処理時間も O(N * logN) です。また、使用されるメモリはO(N)になります。

ちなみに、実際の N は 10^6 ではなく 10^5 であるため、あなたのソリューションも適切です。これにより、ソリューションでタイミングを 2 秒未満に保ち、使用するメモリを 20MB 未満にすることができます。

于 2013-09-05T16:07:56.520 に答える