1

問題：

シルセリの街は完璧に計画されています。都市は、M行N列の長方形のセル配列に分割されています。各セルには地下鉄駅があります。各列に沿って左から右へと後ろに走る列車が1本あり、各列に沿って上から下へと後ろに走る列車が1本あります。各列車はある時間Tに発車し、そのルート（行または列）に沿って永遠に行き来します。

通常の列車は、ある駅から次の駅に行くのに2単位の時間がかかります。ある駅から次の駅まで1単位の時間しかかからない高速列車がいくつかあります。最後に、ある駅から次の駅まで行くのに3単位の時間がかかる遅い列車がいくつかあります。どの駅でも停車時間はごくわずかだと思われるかもしれません。3行4列のメトロシステムの説明は次のとおりです。

S(1) F(2) O(2) F(4)
F(3) . . . .
S(2) . . . .
O(2) . . . .

各行/列の先頭にあるラベルは、列車のタイプ（Fは高速、Oは通常、Sは低速）とその開始時刻を示しています。したがって、列1に沿って移動する列車は高速列車であり、時刻3に開始します。駅（1,1）から開始して右に移動し、それぞれ時刻3、4、5、および6にこの列に沿って駅を訪れます。次に、6、7、8、9の時点で右から左に駅を訪れて戻ります。また、9、10、11、12の時点で、駅を訪れて再び移動します。同様に、列3に沿った列車は、時刻2から始まる普通列車です。したがって、駅（3,1）から出発して、時刻2、4、6に列3の3つの駅を訪れ、の先頭に戻ります。 6、8、10時にそれらを訪問するコラムなど。

出発駅、出発時刻、目的地の駅を考えると、あなたの仕事は、これらの列車を使って目的地に到着できる最も早い時間を決定することです。たとえば、時刻8に駅（2,3）から出発し、駅（1,1）に到達することを目的としているとします。時間8で2列目の低速列車に​​乗り、時間11で（2,4）に到達する場合があります。時間11で、列4の高速列車が（2,4）で上向きに移動しているため、この高速列車に乗って時間12で（1,4）に到達できます。もう一度幸運です。時間12で1列目の高速列車は（1,4）にあるので、この高速列車に乗って（1 、1）時間15。別のルートは、時間8の（2,3）から列3の普通列車に乗り、時間10の（1,3）に到達することです。その後、時間13までそこで待機し、 1列目の高速列車が左に行き、（1、

テストデータ：M、N≤50と想定できます。
制限時間：3秒

N、Mのサイズは非常に小さいので、再帰によって解決することができます。

すべての駅で、目的地に近づくことができる2本の電車に乗ります。
例：2,3から1,1に行きたい場合は、2,3に近づく電車に乗り、目的地に最も近い駅に降ります。目的地に到着し、これまでの最小時間を追跡し、目的地に到達するのにかかる時間が最小時間より短い場合は更新します。

この方法を使用して、特定の時間に列車がどの駅にあるかを判断できます。

/* S is the starting time of the train and N is the number of stations it
 visits, T is the time for which we want to find the station the train is at. 
T always be greater than S*/

T = T-S+1
Station(T) = T%N, if T%N = 0, then Station(T) = N;

これが私の質問です：

  • 特定の列車が目的の駅に目的の方向に到着する最も早い時刻をどのように判断しますか？

  • 上記のアルゴリズムは欲張り戦略を使用しているので、正確な答えが得られますか？そうでない場合、どうすればこの問題に取り組むことができますか？

PS：これは宿題ではなく、オンラインの裁判官の問題です。

4

1 に答える 1

4

ここでは貪欲な解決策は失敗すると思いますが、反例を作成するのは少し難しいでしょう。

この問題は、ダイクストラのアルゴリズムを使用して解決することを目的としています。エッジは隣接するノード間の接続であり、列車のタイプとその開始時刻によって異なります。また、グラフ全体を計算する必要はありません。検討している現在のノードのエッジを計算するだけです。私は多くの同様の問題を解決しました、そしてこれはあなたが解決した方法です。また、それが決して通過しないことを知る前に、貪欲を数回使用しようとしました。

お役に立てれば。

于 2013-01-09T09:18:12.590 に答える