循环马拉松（JBOI 2013）

我一直在试图解决它一段时间，但没有运气......你介意指导我找到解决方案吗？

感谢

可视化问题，我在想是否比较所有对跑步者的距离会有所帮助.... – user2455103

编辑您的问题，并添加您尝试到目前为止有更高机会得到答案。 – CSchulz

一种可能是当前的运动员存储在双向链表（做，一旦他们被淘汰很容易地删除亚军）。

对于第一个跑步者比第二个跑步者要快的连续跑步者，计算他们将会见的时间并将此次存储在堆数据结构中（该堆包含会议时间和指向第二个跑步者的指针）。

该堆将允许您找到下一个参赛者（这将是堆顶部的一对），然后您可以及时更新数据结构O（logn）并重复，直到堆为止空。

的更新将需要：

如果这次会议中的第一名跑步者已经从比赛中删除，那么更新应该跳过。

总的来说，这需要花费时间O（nlogn）。

2014-02-26 19:11:23

是的，这很接近我的想法......我只是意识到，一个跑步者不能消除另一个时，他不是连续的，他必须在这个过程中遇到更多的跑步者。所以，我们只需要找到两名运动员将会见面的时间。 – user2455103

而且......我可以假设它只是尽可能使用优先级队列而不是堆权？ – user2455103

@ user2455103堆是一种优先级队列，当然如果您愿意，可以自由使用不同类型的优先级队列。 –

回答