运用链表更新体育竞赛排名
成绩排名
最近我国正好在举办冬奥会。说实话能在目前的疫情压力下,举办如此优秀的冬奥会,着实让我的国家自豪感倍增。相应的,生活中也经常从各种信息渠道获得冬奥会的信息,具体到笔者个人,我主要是关注了部分之前就比较感兴趣的赛事——冰壶、速滑等。
冰壶因为是一对一的比赛,目前才用的是十几轮的小组循环赛后接淘汰赛。每次比完一场后,就会根据胜负来更新排名。
实际上,许多的体育赛事,或者说大部分的赛事,都允许多次获得成绩取最高,或者成绩由多次累加。那么在其中必然就伴随的每次的排名波动。如果是一天一次更新,那难度不会很大,如果是短时间内选手迅速获得多个成绩,那么对于排名的实时更新的具体实现,就是一个可以充分探讨的问题。
基本描述
先把实际问题精简提炼成数学模型。简单一点。比如说我们现在有 n 个正整数成绩(0~100),每次出现一个成绩,就需要对排名做一次更新,获得前百分之十的分数线。
如果有一定的语法基础的话,可能现在一个基础的解法就已经在读者你心里诞生了——那就是纯粹的模拟:
然后每次输出前 10% 的 rank 即可。
问题转化
很明显的一点,我们至少需要双重循环,也就是 o(n^2) 的复杂度。因为 n 的成绩的读入,以及每次读入成绩后,更新排名的过程也是 o(n) 的。
我猜已经有读者想到了另外一种的策略,那就是链表。因为链表维护插入和删除的过程是 o(1) 的。但是链表还是不对。因为每次都仍然有找到合适位置的过程。这个过程极端一些,每次都是最后一名,那单次查询的复杂度仍然是 o(n) 的。
我们会发现这个问题同时对查询和插入都有要求。
仔细想想,还有什么东西我们没有注意到。
回到问题,“有 n 个正整数成绩(0~100)”,不知道读者是否对这句话有敏感——数字范围太小了,只有仅仅 100 个。所以我们准备采用桶数组来维护。
桶数组
桶数组简单来说便是把相同的事物存放在一起。也就是说,把成绩相同的人放在一起,我只需要从高到低维护每个分数有多少人即可。
那么现在如何维护前 10% 呢?
我们只需要把分数从高到低遍历一遍,然后统计人数,只要超过 10% 就停止输出。
零基础程序语言入门班
零基础程序语言入门班详情介绍
学员要求
对编程有兴趣,零基础的孩子。
上课时间
每周日下午2-5点
上课地点
福田区百花新天地3楼
师资介绍
何老师,计算机专业硕士保送生,现役ACM-ICPC队员,今年获得ICPC银川站金牌,CCPC银牌,EC铜牌以及邀请赛金牌。何老师不仅参赛成绩斐然,在教学上也有丰富经验,曾担任2019年CSP-S提高组集训班老师,以及数据结构专题班老师,教学细致耐心。
课表详情:
详情可扫描二维码联系郑老师咨询了解
毕莘教育咨询(深圳)有限公司围绕信息学竞赛普及组、提高组、省赛、国赛进行培训,同时提供与信息学相关的高校自主招生政策咨询。教研团队由国内顶校师资构成,深圳本地教学团队由来自清华、北大等顶尖名校的硕士、博士研究生及NOI、ACM- ICPC退役选手组成。自成立已开展多次培训,服务学生数百人次。
原创文章,作者:深圳信息学_中小学编程_编程培训_信息学竞赛_毕莘教育咨询(深圳)有限公司,如若转载,请注明出处:深圳信息学_中小学编程_编程培训_信息学竞赛_毕莘教育咨询(深圳)有限公司