【题解】洛谷P1309瑞士轮

题目

洛谷P1309瑞士轮

题解

此题要求对特殊数据定制更高效的排序方法,常规的排序算法都会超时。

此题关键在于发现数据的性质:在每轮比赛后,胜者的相对位次不变(全体分数+1),败者的相对位次也不变。然后,就能得到两条单调的数列,只要合并即可。这项操作与归并排序中的合并操作相似。由于数据类型是struct,不方便直接进行操作(其实很方便,把tmp1[],tmp2[]都换成struct型即可),所以采用表排序(即间接排序),对数据的编号(下标)进行操作。

代码

Subscribe
提醒
guest
2 评论
Oldest
Newest Most Voted
Inline Feedbacks
View all comments
cyx
cyx
2020年8月13日 下午3:50

【小白解析】
此题思路较为直白,不多赘述。
解法实际将每一局中的胜者与败者分别储存在两个数组中,通过归并排序的方法将两数组中的选手逐个“扫”入原数组中。值得注意的是,选手的分数在最开始已被快速排序,因而不用担心最初的顺序问题。