algorithm - 自行车马拉松 (JBOI 2013)

Question

<分区>

Answer 1

一种可能性是将当前运行者存储在双向链表中(以便在运行者被淘汰后轻松删除运行者)。

对于每对第一名比第二名更快的连续运行者，计算他们相遇的时间并将这个时间存储在堆数据结构中(堆包含相遇时间和指向第二名运行者的指针) .

堆将允许您找到下一个运行者(这将是堆顶部的一对)，然后您可以及时更新您的数据结构 O(logn) 并重复直到堆为空.

更新需要:

1. 标记第二名选手已不在比赛中
2. 从链表中移除第二名
3. 将新的集合时间从第一个运行者添加到列表中的下一个(仅当第一个运行者足够快时)
4. 重新平衡堆

如果本次 session 的第一名参赛者已从比赛中移除，则应跳过更新。

总的来说，这需要时间 O(nlogn)。