运用链表更新体育竞赛排名
成绩排名
最近我国正好在举办冬奥会。说实话能在目前的疫情压力下，举办如此优秀的冬奥会，着实让我的国家自豪感倍增。相应的，生活中也经常从各种信息渠道获得冬奥会的信息，具体到笔者个人，我主要是关注了部分之前就比较感兴趣的赛事——冰壶、速滑等。
冰壶因为是一对一的比赛，目前才用的是十几轮的小组循环赛后接淘汰赛。每次比完一场后，就会根据胜负来更新排名。
实际上，许多的体育赛事，或者说大部分的赛事，都允许多次获得成绩取最高，或者成绩由多次累加。那么在其中必然就伴随的每次的排名波动。如果是一天一次更新，那难度不会很大，如果是短时间内选手迅速获得多个成绩，那么对于排名的实时更新的具体实现，就是一个可以充分探讨的问题。
基本描述
先把实际问题精简提炼成数学模型。简单一点。比如说我们现在有 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退役选手组成。自成立已开展多次培训，服务学生数百人次。
原创文章，作者：深圳信息学_中小学编程_编程培训_信息学竞赛_毕莘教育咨询（深圳）有限公司，如若转载，请注明出处：深圳信息学_中小学编程_编程培训_信息学竞赛_毕莘教育咨询（深圳）有限公司
