Enhanced FrogRiverN

Question

私はいくつかのプログラミング演習を行っています。これはかなりよく知られており、さまざまな場所で答えられています。

FrogRiverOne カエルが川の反対側に飛ぶことができる最も早い時期を見つけます。 https://codility.com/programmers/task/frog_river_one/

私の質問は、カエルがDの距離をジャンプすることができますか？どのように川を渡る最短の時間を見つけることができます最高の実行時の複雑さで？ありがとう！

int solution(int X, vector<int> &A, int D); // frog can jumps from 1 to D steps 

Answer 1

私はショールの貪欲な解決策はほぼ正しいと思います。 Current_Posを変更したときに再帰的伝搬ステップを含めると、カエルは常に最前面に配置されます。ここで

は再帰を避ける代替手段です：

は葉がある場合、それぞれの位置のために保存する占有配列を使用してください。また、すべての位置にノードを持つユニオン検索データ構造を使用します。ユニオンファインドデータ構造は、互いに到達可能なノード（すなわち、接続されたコンポーネント）を追跡する。この作業は、両方の河川がつながっている最初の時点を見つけることです。

これを見つけるには、次の手順を実行します。新しいリーフが場に出るたびに、その位置を占有としてマークします。次に、この位置から到達可能なすべての占有ノード（-D〜+D）とユニオン検索データ構造内のノードを結合します。最後に、両方の河川が接続されているかどうかを確認します。全体の時間複雑度はO(ND+X)です。

どちらが速いのかは、入力に依存します。