ヒープと配列を使用して次の問題を解決しようとしています。
ガソリンスタンドがランダムに配置されたループが与えられたとします。すべてのステーションで、ループを一周するのに十分な量のガスが組み合わされています。あなたは空の車から始めます。出発して戻ってくる (ループを終了する) ことができる駅をすべて見つけます。一方向にしか行けないと仮定します (それは問題ではありません)。また、ガソリンタンクが無制限で、mpg が常に一定であると仮定します。
私が思いついた解決策は、最小ヒープを構築し、0 から n-1 までの値を持つ配列をこの順序で配置して、位置を表すことです。
まず、ガソリンを走行距離に換算し、そこから次の駅までの距離を引きます。配列になってしまいます。それらを V[0]、V[1]、...V[n-1] と呼びます。
次に、配列の 1 は V[0] を指し、m は sum(V[0],...V[m-1]) を指し、0 は sum(V[0]...V[n- 1]）。
合計は最小ヒープに配置されます。
これが完了すると、最小値が指す配列内のすべてのインデックスが解になります。
次に、1 が指す合計を調べて次の構成に回転し、sum(V[0]..V[n-1]) を追加します。再加熱する。新しい最小値が出現した場合 (最小値が合計によって作成された場合のみ)、新しい最小値が指す配列で新しい解を検索します。
私の質問は、配列とヒープの間のリンクを異なる言語でどのように実装するかです。
ありがとう。