Freda越野跑

Freda的越野跑经历

提示

将这五位参与者依次标记为A、B、C、D、E，其行进速度分别为1、3、10、8、5。
在跑步过程中：
B、C、D、E均会超越A，因其速度均高于A；
C、D、E也将超越B，因其速度均高于B；
至于C、D、E之间，则不会出现超越现象，因速度较快者在起跑时已处于前方位置。

思路：

这不就是计算正序对的问题吗？与之前计算逆序对的思路非常相似（这道题也可以使用队列来解决，不过由于未排序，实现起来并不方便）！

实际上，这个“超过”的过程，正是在模拟基于比较的排序算法中元素交换的过程。因此，我们所需要完成的任务是统计整个排序过程中发生的交换次数。（最直观的例子就是冒泡排序，速度较快的元素会被交换到前面，每一次交换就相当于超过一个人）
需要注意的是，对于速度相同的个体而言，后面的元素不会超越前面的元素。因此，在这种情况下我们需要采用一种稳定的排序算法。同时考虑到数据规模的限制，我们需要选择时间复杂度为O(nlogn)的算法，因此自然而然地会选择归并排序。

在归并排序过程中需要记录的交换次数发生在合并左右两个子序列时。如果左子序列中还有剩余元素而先将右子序列中的一个元素放入结果序列中，则意味着右子序列中的该元素已经超过了左子序列中剩余的所有元素。这就是我们需要记录的内容。

另