第1次看到这题的时候断言这题很水,后来发现安徽最高60分,有回头仔细看看,发现的确非常难做。
首先是排序中有三个量和两个关键字,代码不由得就复杂起来,加上我用Anjuta还不是很熟,写得非常痛苦。
一开使选择对序号进行排序,就是序列X【i】表示排名第i的选手的编号,这样的想法是好的,但写起来要非常细致,最后就变繁琐了。
然后又选择了对两个关键字进行依次比较排序,也是写得很烦,最后发现归并排序其实是稳定的排序,根本就不需考虑第二关键字......
这题的算法也比较难想,我想了大概有一个小时才想到满分的算法(直接排序50%的就不说了)
我一开始想到对于每一轮比赛结束,每个人的分数最多增加1,那么每一个人的名次上升的空间是有限度的,
我们可以考虑一种线性的维护方法,使整个序列仍然是有序的,但因为是双关键字,考虑起来实在比较复杂,就放弃了(这个要继续思考!)
让后就想到了归并的思想,把两个有序的序列合并。很显然,对于在该轮中全部输的人,他们之间的相对排名不会发生变化,
对于在该轮中全部赢的人,也有同样的性质。所以每次对于每轮比赛结束,只要用O(n)的时间就能让整体变成有序的了。
注意:选手是有初始分数的,第一轮要先排一次序。