由于每次比赛完都要通过得分和编号来进行排序,但是要比赛 r 次,用快速排序也比较慢,这个时候,可以想到每次比赛之后,得到的两个数组都是有序的,因此可以使用归并排序的 merge 操作,使得排序时候由 O(nlgn) 优化到 O(n)。
这里我们使用结构体,保存每个选手的编号,得分,能力,一开始通过编号和得分排序。
然后每轮比赛,让相邻的两个选手进行比较,这里比较就需要使用能力比较,然后胜利者进行得分,把胜利者和败者分别放在两个数组里,这样能保证两个数组都是有序的,就可以使用 merge 函数进行合并有序数组,优化排序时间,然后进行下一轮比赛。
merge 函数中比较是通过得分进行比较的,注意区分。