c++&oi

NOIP2011普及组的第三题:瑞士轮

第1次看到这题的时候断言这题很水,后来发现安徽最高60分,有回头仔细看看,发现的确非常难做。
首先是排序中有三个量和两个关键字,代码不由得就复杂起来,加上我用Anjuta还不是很熟,写得非常痛苦。
一开使选择对序号进行排序,就是序列X【i】表示排名第i的选手的编号,这样的想法是好的,但写起来要非常细致,最后就变繁琐了。
然后又选择了对两个关键字进行依次比较排序,也是写得很烦,最后发现归并排序其实是稳定的排序,根本就不需考虑第二关键字......

这题的算法也比较难想,我想了大概有一个小时才想到满分的算法(直接排序50%的就不说了)

我一开始想到对于每一轮比赛结束,每个人的分数最多增加1,那么每一个人的名次上升的空间是有限度的,
我们可以考虑一种线性的维护方法,使整个序列仍然是有序的,但因为是双关键字,考虑起来实在比较复杂,就放弃了(这个要继续思考!)
让后就想到了归并的思想,把两个有序的序列合并。很显然,对于在该轮中全部输的人,他们之间的相对排名不会发生变化,
对于在该轮中全部赢的人,也有同样的性质。所以每次对于每轮比赛结束,只要用O(n)的时间就能让整体变成有序的了。
注意:选手是有初始分数的,第一轮要先排一次序。

posted on 2011-12-04 16:57 zyn.cpp 阅读(2632) 评论(2)  编辑 收藏 引用

评论

# re: NOIP2011普及组的第三题:瑞士轮 2011-12-07 18:01 又四天

有代码吗?
  回复  更多评论   

# re: NOIP2011普及组的第三题:瑞士轮 2011-12-10 15:48 zyn.cpp

@又四天
本来有一个快排补丁版的,后来把它改成归并了,结果只有40%。  回复  更多评论   


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   博问   Chat2DB   管理


<2024年12月>
24252627282930
1234567
891011121314
15161718192021
22232425262728
2930311234

导航

统计

常用链接

留言簿

随笔档案(57)

文章档案(13)

搜索

最新评论

阅读排行榜

评论排行榜