Educational Codeforces Round 109 Robot Collisions 题解(Java/C++)

题意

有n个机器人分布于0到m之间。这些机器人从他们初始位置开始可能往左走也可能往右走。碰壁之后自动回头。如果某一个整秒,两个机器人处于同一个位置,则这两个机器人爆炸。问这些机器人的爆炸时间。


题解

首先,对于任意两个机器人$i$和$j$,如果$x_i\equiv x_j\mod 2$,则这两个机器人迟早撞上。否则永远撞不上。
假设某一个时刻t后,$x_i+t=m-1$。显然$x_i+t\equiv x_j+t\mod 2$依然成立。考虑$x_i$用2秒折返,显然$x_i+t\equiv x_i+t+2\equiv x_j+t \equiv x_j+t+2 \mod 2$。
于是,不论如何,只要$x_i\equiv x_j\mod 2$,就一定能撞上。


于是我们将所有的机器人按初始位置的奇偶数分开处理。对于其中的任意一部分的机器人:

我们首先考虑往右走的机器人。这个机器人有两种爆炸的可能:1. 这个机器人的右边有往左的机器人。2. 这个机器人的右边有往右,并且没有爆炸的机器人。
这两种情况的前提是:这个最终从右边撞过来的机器人和掉头的机器人都不会提前和其他机器人相撞。

进一步考虑第二种情况我们发现,这个掉头后往左的机器人的位置可以等价为$m+(m-x_i)$出发,直接往左走。($m+(m-x_i)$记为realPos,对于本来就往左的机器人realPos等于初始位置)
同时我们注意到,这个掉头往左的机器人本身一定找不到往左的机器人和他配对。不论是因为他右边本来就没有机器人,还是他右边的机器人已经爆炸了。

于是,我们从右往左依次检查每一个机器人。
如果这个机器人本来就是往左的,那我们把他加入优先队列中,等待和其他往右的机器人配对。
如果这个是往右的,那么找到realPos最左的机器人,进行配对。如果没有往左的机器人,那么计算当前机器人的realPos,并假如优先队列,等待和其他往右的机器人配对。
最后对于队列中剩下的机器人,由于都是往左的。那么他们一定能两两配对,且配对的方式一定是一个在最左边掉头之后和另一个相撞。(注意:这里计算的时候应该以考虑了在最右边掉头的可能性后的realPos计算)


代码

Java

Submission #116422177 - Codeforces
Codeforces. Programming competitions and contests, programming community

C++

Submission #116428296 - Codeforces
Codeforces. Programming competitions and contests, programming community
展示评论