循環馬拉松（JBOI 2013）

我一直在試圖解決它一段時間，但沒有運氣......你介意指導我找到解決方案嗎？

感謝

可視化問題，我在想是否比較所有對跑步者的距離會有所幫助.... – user2455103

編輯您的問題，並添加您嘗試到目前爲止有更高機會得到答案。 – CSchulz

一種可能是當前的運動員存儲在雙向鏈表（做，一旦他們被淘汰很容易地刪除亞軍）。

對於第一個跑步者比第二個跑步者要快的連續跑步者，計算他們將會見的時間並將此次存儲在堆數據結構中（該堆包含會議時間和指向第二個跑步者的指針）。

該堆將允許您找到下一個參賽者（這將是堆頂部的一對），然後您可以及時更新數據結構O（logn）並重復，直到堆爲止空。

的更新將需要：

如果這次會議中的第一名跑步者已經從比賽中刪除，那麼更新應該跳過。

總的來說，這需要花費時間O（nlogn）。

2014-02-26 19:11:23

是的，這很接近我的想法......我只是意識到，一個跑步者不能消除另一個時，他不是連續的，他必須在這個過程中遇到更多的跑步者。所以，我們只需要找到兩名運動員將會見面的時間。 – user2455103

而且......我可以假設它只是儘可能使用優先級隊列而不是堆權？ – user2455103

@ user2455103堆是一種優先級隊列，當然如果您願意，可以自由使用不同類型的優先級隊列。 –

回答