亡者行走
Dead Men Walking
题目详情
有 100 只僵尸站在一条直线上，相邻僵尸间距均为 1，且每只僵尸以相同速度行走。有的向左走，有的向右走。
当两只僵尸相撞时，它们会同时掉头（反向行走）。
已知每只僵尸初始向左/向右的方向，问：能否预测总碰撞次数？
提示：把“相撞后掉头”视为“直接穿过彼此继续走”。
Assume 100 zombies are walking on a straight line, all moving with the same speed. Some are moving towards left, and some towards right. If a collision occurs between two zombies, they both reverse their direction. Initially all zombies are standing at 1 unit intervals. For every zombie, you can see whether it moves left or right, can you predict the number of collisions?
Hint
On every collision, assume that the two zombies don't reverse direction but simply cross each other.
解析
可以。
把碰撞理解为两只僵尸“直接穿过”并交换身份，则每次“相向而行的邻对”会对应一次碰撞。
因此总碰撞次数等于：对每一只向右走的僵尸，统计其右侧向左走的僵尸数量，并把这些数量求和。
等价于统计方向序列中的“逆序对”数量（R 在前、L 在后）。
Original Explanation
Solution
Since we can assume that zombies can pass through each other, for a zombie moving right, count the number of zombies to its right moving left. Add this number for every right moving zombie. That is the number of collisions.