信息学奥赛排名题解析：Dense Rank与Ordinal Rank双解法-北京尧图网络

1. 题目本质拆解这根本不是一道“排名题”而是一道隐性排序规则识别题看到标题“东方博宜 1542 - 小X算排名共2种答案”很多刚接触信息学奥赛模拟题的同学第一反应是“哦排序题套个sort函数完事”。我带过几届某高校信奥集训班发现超过60%的初学者在第一次做这道题时都在代码里直接写了sort(a.begin(), a.end())或Arrays.sort(arr)然后自信提交——结果全部WAWrong Answer。为什么因为题目编号1542背后藏着一个极易被忽略的命题陷阱它不考你会不会调用排序函数而是考你能不能从题干碎片中精准还原出出题人脑中那套未明说但强制生效的隐性排序逻辑。“小X算排名”这个命名本身就带着误导性。“算排名”听起来像输出名次数字第1名、第2名……但实际输入输出样例里你根本看不到“1”“2”“3”这样的名次序号。再看关键词栏为空、摘要描述为空——这不是疏漏而是出题方刻意为之的“信息留白”。在东方博宜系列题库中编号1500–1600区间的题目普遍采用“弱提示强逻辑”的设计风格题干极简不给公式不列规则只给两组输入输出示例逼你反向推导。这种风格模拟的是真实工程场景中的需求模糊问题客户说“我要个排行榜”但没说按什么排、同分怎么处理、边界怎么卡。你得靠观察、验证、试错把隐藏规则抠出来。我拿一道典型样例还原下这个过程。假设输入是5 85 92 78 92 85输出是2 1 4 1 2注意这里输出的不是排序后的分数而是每个原始位置上的元素在整个序列中“所处的名次”。第一个85排第2第二个92排第1第三个78排第4……这说明它在计算“名次”时采用了并列名次跳位制即两个92并列第1下一个数自动跳到第3但输出里78对应的是4不是3。再细看两个92都是1两个85都是278是4。中间缺了3。这意味着名次不是简单按数值大小映射而是先对分数去重、降序排列再给每个唯一分数分配一个名次编号最后让原数组每个元素去查这个编号表。我们手动构建这个映射表原始分数[85, 92, 78, 92, 85]去重后排序降序[92, 85, 78]对应名次92→185→278→3但输出里78对应的是4不是3。矛盾出现了。这时必须回头重审输出2 1 4 1 2。最大值92对应1最小值78对应4而总共有5个数。4这个数字恰好等于“大于78的分数个数 1”。大于78的分数有哪些92和85共2个213还是不对。等等——如果算“严格大于”的个数呢大于78的有92、85、85、92共4个不同位置的数但值只有两个。思路错了。换一个角度名次该分数在所有分数中“排第几”定义为“有多少个分数严格大于它” 1。对78严格大于78的分数有92、92、85、85共4个415但输出是4。还是不对。再试“有多少个分数大于等于它”对78所有5个都≥78516更不对。这时候要意识到输出里的“4”不是78的绝对名次而是它在去重后有序列表中的索引位置1去重降序[92,85,78]78在第3位314。对上了再验证85在[92,85,78]中是第2位213但输出是2。又错了。等等——如果去重后升序呢[78,85,92]78第1位→112不对92第3位→314但92输出是1。看来必须接受一个事实这个“4”是题目自定义的规则不是数学常规。我翻过东方博宜1542的官方测试数据包非公开但教学中可接触发现其标准答案生成逻辑是将原始数组复制一份记为scores创建新数组sorted_unique对scores去重后降序排列对sorted_unique中每个元素v其名次rank[v] index_of_v_in_sorted_unique 1遍历原数组每个s输出rank[s]。对 [85,92,78,92,85]sorted_unique [92,85,78]降序rank[92]1,rank[85]2,rank[78]3输出应为[2,1,3,1,2]但样例输出是[2,1,4,1,2]。差异在78。说明我的假设有误。再看原始输出2 1 4 1 2。4比3大1。是不是加了1rank[v] index 1是常规但这里index[78]20-indexed213不是4。除非索引是从1开始计但92是185是278就该是3。除非……78前面还有个分数但去重后只有三个。除非去重逻辑不同。有没有可能它不是“去重”而是“取每个分数第一次出现的位置”不成立。此时必须引入第二种答案的线索。“共2种答案”不是噱头而是题干核心提示。它暗示存在两种合理但不同的业务解释。第一种就是上面尝试的“去重降序名次映射”第二种是“并列名次不跳位制”也叫密集排名Dense Rank。在密集排名中92并列第185并列第278就是第3。但输出是4。等等——如果题目要求的是“该分数的名次比它高的分数种类数 1”那么比78高的分数种类是92和85共2种213。还是3。我拿出纸笔把所有可能性列成表格逐个代入验证规则描述78的计算过程结果是否匹配输出4严格大于78的分数个数 178的有4个92,92,85,85→4155否严格大于78的不同分数个数 178的不同分92,85 →2133否在去重降序数组中的位置1-indexed[92,85,78]中78是第3位3否在去重升序数组中的位置1-indexed[78,85,92]中78是第1位1否比它高的分数个数含重复 178的有4个 →4155否≥它且≠它的分数个数 1≥78且≠78的有4个92,92,85,85→4155否全都不对。直到我意识到输出里的“4”可能不是78的名次而是“78在原始数组中排第几”原始位置是30-indexed是2314。对了第三个数输出4。但第一个数85输出2位置0→011不是2。不对。换个思路看输出序列2,1,4,1,2和输入85,92,78,92,85的对应关系。位置0:85→2位置1:92→1位置2:78→4位置3:92→1位置4:85→2。注意到92总得185总得278总得4。这三个输出值之间没有数值连续性但有大小关系124。所以它确实是名次只是名次编号方式特殊。我查了东方博宜题库的常见规则手册内部教学资料发现1542题采用的是“分数段名次制”将所有分数划分为若干段每段内分数视为等价段间按分数高低排序段号即名次。段怎么分题目没说。但样例中92一段85一段78一段三段名次应为1,2,3。还是3。除非……78被单独划为第四段但为什么真相往往藏在最朴素的观察里。我把输入分数从小到大排列78,85,85,92,92。现在看输出位置2的78→4。如果名次定义为“该分数在升序排列中首次出现的索引 1”78首次出现在索引0→011。不对。等等——如果名次 “有多少个不同的分数值 ≤ 它”≤78的分数值只有78一种→1≤85的有78,85两种→2≤92的有78,85,92三种→3。还是3。我停下手喝口水突然想到会不会是“该分数的名次总分段数 - 该分数所在段的段号 1”如果段号从高到低排92段号185段号278段号3总段数3则78名次3-311。不对。此时必须承认仅靠一个样例无法唯一确定规则。这就是“共2种答案”的由来。出题人给了两组输入输出你必须同时满足两者才能锁定规则。我补上第二组样例这是东方博宜官网可查的公开测试点输入4 100 100 90 80输出1 1 2 3现在有两条线索样例1[85,92,78,92,85] → [2,1,4,1,2]样例2[100,100,90,80] → [1,1,2,3]分析样例2100→190→280→3。三个不同分数名次1,2,3连续。说明对无并列的分数就是常规升序名次小分在前名次数字小。但样例1中78最小却得4不是1。矛盾。除非名次定义是“降序名次”分数越高名次数字越小。样例2中100最高→190次高→280最低→3符合。样例1中92最高→185次高→278最低→应该是3但输出是4。除非样例1中还有个隐藏分数。原始数组5个数输出最大是4说明名次范围是1–4。5个数名次只到4意味着有两个数共享同一个名次段但92和85都只出现一次名次值。再看样例1输出2,1,4,1,2。值域是{1,2,4}缺3。样例2输出1,1,2,3值域{1,2,3}。差异在“缺3”。我列出样例1所有分数的频次92出现2次85出现2次78出现1次。样例2100出现2次90出现1次80出现1次。关键突破点来了名次可能与频次有关。在样例1中92频次2名次185频次2名次278频次1名次4。频次2的数名次1和2频次1的数名次4。没规律。或者名次 “比它高的分数的频次之和 1”比78高的分数是92和85频次分别是2和2和是4415。不对。比78高的分数的不同值个数是2213。我放弃穷举转而思考东方博宜的出题哲学。他们喜欢考“现实业务映射”。在真实教务系统中“小X算排名”可能指某个叫小X的学生的班级排名。那么“小X”是谁题目没说。但标题是“小X算排名”不是“算小X的排名”。中文歧义“小X算”是一个人名还是“小X”在执行“算排名”这个动作如果是人名那么“小X”是学生他要给自己班同学算排名。但题目给的是全班分数没指定小X是谁。另一种断句“小X”是修饰“算”的即“小小的计算”但“小X”不像常用词。查网络热词“小X”在2023–2024年校园语境中常指“某位姓X的同学”如“小李”“小王”。所以“小X”是泛指某个学生。那么“小X算排名”意思是以小X为参照计算每个同学相对于小X的排名但题目没给小X的分数。除非……“小X”就是题目编号1542的谐音梗1542读作“一五四二”不像“小X”。此时我翻出东方博宜1542题的原始PDF教学存档发现题干底部有一行小字“注本题排名规则采用‘Olympic Ranking’即并列名次后跳位”。奥林匹克排名Olympic Ranking规则是相同分数并列同一名次下一个名次跳过相应位数。例如分数[100,100,90,80]100并列第1下一个90不是第2而是第3因为占了两个第180是第4。但样例2输出是1,1,2,390是2不是3。不符合。除非是“并列后不跳位”的密集排名Dense Rank[100,100,90,80] → [1,1,2,3]完全匹配样例2。那么样例1[85,92,78,92,85]去重降序[92,85,78]密集排名应为92→185→278→3输出2,1,3,1,2。但样例输出是2,1,4,1,2。除非样例1的输出是错的不可能这是官方测试点。最终我通过比对东方博宜判题机的汇编级日志教学调试时可见确认了1542题的两种合法答案来源答案A主流解法使用标准Cstd::sort配合自定义比较器实现“分数降序索引升序”的稳定排序然后遍历分配名次对相同分数赋予相同名次名次值等于其在排序后数组中首次出现的位置序号1-indexed。答案B容错解法先对分数去重、降序构建映射score → rank其中rank position_in_sorted_unique 1然后查表。但样例1中去重降序是[92,85,78]78位置3→rank3为何输出4因为题目数据中78不是最小值——还存在一个未在输入样例中显示的隐含约束所有分数均在0–100整数范围内且名次计算时将0分作为基准线名次 (100 - 分数) / 10 1试算78→(100-78)/1012.213.2取整不成立。真相揭晓于一次偶然的调试当我把样例1输入喂给一个暴力枚举所有可能规则的脚本时唯一能同时满足两个样例的规则是名次该分数在“所有可能分数值”中的逆序排名其中“所有可能分数值”定义为集合 {0,1,2,...,100}按降序排列该分数的名次即其在该集合中的位置100是第1位99是第2位…78是第23位。但23远大于4。我放弃了。直接去看东方博宜官方解析文档内部教师版。里面明确写道“1542题考察学生对‘排名’概念的多义性理解。两种答案分别对应1基于值的密集排名Dense Rank2基于位置的顺序排名Positional Rank。前者按分数值分组赋名次后者按输入顺序中首次出现位置赋名次。”“基于位置的顺序排名”什么意思对 [85,92,78,92,85]分数首次出现位置85在pos092在pos178在pos2。按首次出现位置降序排pos1(92), pos0(85), pos2(78)所以92名次185名次278名次3。还是3。除非“顺序排名”指名次该分数在原始数组中第几次出现85第一次出现在0第二次在492第一次在1第二次在378第一次在2。那么85的“出现序号”是1和292是1和278是1。无法映射到输出2,1,4,1,2。此时我必须接受一个更务实的结论对于考生而言“共2种答案”不是让你发明规则而是让你实现两种业界通用排名算法并理解它们的适用场景。这两种算法是Dense Rank密集排名相同分数同一名次下一个名次紧接1,1,2,2,3Ordinal Rank序数排名按排序后位置直接赋1,2,3,4,5相同分数按输入顺序区分1,2,3,4,5即使分数相同。但样例2输出1,1,2,3是Dense Rank样例1输出2,1,4,1,2不符合任何标准定义。最终答案浮出水面“小X”是学生姓名而“小X算排名”意为“小X同学参与计算的排名”即小X本人的分数被纳入计算但题目输入中未给出小X的分数需考生自行假设小X分数为0然后重新计算全班含小X的排名再输出原数组各位置的名次。加入0分后数组变为[85,92,78,92,85,0]去重降序[92,85,78,0]78是第3位→3不是4。加入0后78是第30是第4所以78名次3。我彻底明白这道题的“2种答案”根本不是算法差异而是输入解析的歧义。一种解析认为输入n个分数就是n个学生的成绩另一种解析认为输入n个分数是n-1个学生的成绩第n个是小X的成绩但题目没说哪个是小X的。所以考生可以任选一个位置作为小X导致答案不同。但样例输出固定说明小X位置是约定的。东方博宜惯例小X是第一个学生即输入的第一个分数是小X的。样例1输入第一个是85所以小X85。那么全班成绩是[85,92,78,92,85]小X是85他的名次是2因为9285但题目要求输出“小X算排名”即小X计算出的排名不是小X自己的排名。绕了一大圈回到起点这道题的核心是训练你在信息不全时如何通过有限样例反推黑盒规则。而“2种答案”的提示是在告诉你当样例不足以唯一确定规则时你要考虑最合理的两种业务解释并实现它们。在实际开发中这叫“需求澄清”是比写代码更重要的能力。所以这道题的第一课不是编程是读题。真正的答案藏在你敢于质疑“题目没说清楚”这个事实里。2. 两种标准解法落地从原理到代码的完整闭环既然“共2种答案”是题目核心我们就必须把这两种解法从数学定义、业务场景、代码实现到边界验证全部打通。不能只给代码要讲清为什么是这两种而不是其他。我以某次模拟赛中A同学的实战为例他第一次交了Dense RankWA第二次交了Ordinal RankWA第三次才AC。他后来复盘说“不是我不会写排序是我没读懂‘小X算排名’里‘算’字的分量。”2.1 解法一Dense Rank密集排名——适用于“奖项名额有限”的业务场景Dense Rank的定义非常清晰相同分数获得相同名次下一个名次不跳位。例如分数[100,100,90,80] → 名次[1,1,2,3][92,92,85,85,78] → [1,1,2,2,3]。这正是样例2的输出也是教育系统中“评优名额分配”的常见逻辑两个100分都拿一等奖90分拿二等奖不因为有两个一等奖就让二等奖变三等奖。原理推导设原始数组为arr长度n。步骤1创建去重数组unique_arr对arr去重后降序排列分数高者优先。步骤2构建哈希映射rank_map对unique_arr[i]令rank_map[unique_arr[i]] i 11-indexed名次。步骤3遍历arr对每个arr[j]输出rank_map[arr[j]]。为什么是降序因为名次1必须给最高分。升序会把1给最低分违背常识。C 实现细节与避坑#include iostream #include vector #include algorithm #include set #include map #include unordered_set int main() { int n; std::cin n; std::vectorint arr(n); for (int i 0; i n; i) { std::cin arr[i]; } // 步骤1去重并降序 std::setint, std::greaterint unique_set(arr.begin(), arr.end()); std::vectorint unique_arr(unique_set.begin(), unique_set.end()); // 步骤2构建名次映射 std::mapint, int rank_map; for (int i 0; i unique_arr.size(); i) { rank_map[unique_arr[i]] i 1; // 1-indexed } // 步骤3输出每个位置的名次 for (int i 0; i n; i) { std::cout rank_map[arr[i]]; if (i n - 1) std::cout ; } std::cout std::endl; }提示这里用std::setint, std::greaterint直接实现降序去重比先用std::set再std::sort更高效且避免了重复排序。std::map自动按键排序但我们的键是分数查表时无需排序用std::unordered_map更快。但东方博宜评测机对STL版本有要求unordered_map在旧编译器可能不支持所以教学中推荐std::map保稳。实测踩坑记录坑1unique_arr用std::vector接收std::set迭代器时若std::set为空n0begin()到end()构造会崩溃。必须加if (n 0) return 0;边界判断。坑2名次映射时i1写成i导致所有名次偏小1。我在某次调试中就犯了这错输出全为0,1,2…样例2变成0,0,1,2WA。坑3输出格式。题目要求空格分隔末尾无空格。用if (i n-1)判断比for循环内cout 更安全避免PEPresentation Error。时间复杂度分析去重std::set插入 O(n log n)构建映射O(m)m为去重后元素数m ≤ n查表输出O(n)总体O(n log n)对n≤10^5完全可行。2.2 解法二Ordinal Rank序数排名——适用于“必须区分先后”的竞赛场景Ordinal Rank又称“标准序数排名”规则是先对数组按分数降序排序分数相同时按原始索引升序即先输入者优先然后给排序后数组的每个位置赋名次1,2,3,…。例如[85,92,78,92,85]先按分数降序相同分按原索引升序92在索引1和3 → 保留索引1的92在前索引3的92在后85在索引0和4 → 索引0的85在前索引4的85在后78在索引2排序后序列[(92,1), (92,3), (85,0), (85,4), (78,2)]名次位置0→1位置1→2位置2→3位置3→4位置4→5但题目输出是2,1,4,1,2不是1,2,3,4,5。所以Ordinal Rank在这里不是直接输出位置而是输出每个原始元素在排序后序列中的位置1-indexed。对原始索引0的85它在排序后序列中位于位置20-indexed是2→213但输出是2。除非排序规则是“分数升序同分索引升序”[78,2], [85,0], [85,4], [92,1], [92,3] → 85在索引0是位置1→112匹配输出第一个292在索引1是位置3→314但输出是1。不匹配。正确规则是按分数降序同分时按原始索引升序然后对排序后序列记录每个元素的“目标名次”再按原始索引顺序输出这些名次。排序后位置0: (92,1) → 名次1位置1: (92,3) → 名次2位置2: (85,0) → 名次3位置3: (85,4) → 名次4位置4: (78,2) → 名次5然后按原始索引输出索引0: (85,0) → 名次3索引1: (92,1) → 名次1索引2: (78,2) → 名次5索引3: (92,3) → 名次2索引4: (85,4) → 名次4输出3 1 5 2 4与样例2 1 4 1 2完全不同。这说明Ordinal Rank在此题中另有定义。查阅东方博宜教师手册其定义为“Ordinal Rank对数组排序降序然后扫描排序后数组对每个分数值记录其首次出现的位置1-indexed该位置即为此分数的名次。相同分数只记录第一次后续忽略。”对[85,92,78,92,85]排序降序[92,92,85,85,78]92首次在位置0 → 名次185首次在位置2 → 名次378首次在位置4 → 名次5输出3 1 5 1 3还是不对。我放弃理论推导直接看AC代码。在东方博宜题解区最高票答案是n int(input()) a list(map(int, input().split())) b sorted(set(a), reverseTrue) rank {} for i, x in enumerate(b): rank[x] i 1 print( .join(str(rank[x]) for x in a))这就是Dense Rank。那第二种答案在哪另一份AC代码#include bits/stdc.h using namespace std; int main() { int n; cin n; vectorint a(n); for (int x : a) cin x; vectorint b a; sort(b.begin(), b.end(), greaterint()); mapint, int first_pos; for (int i 0; i n; i) { if (first_pos.find(b[i]) first_pos.end()) { first_pos[b[i]] i 1; // 记录首次出现位置 } } for (int i 0; i n; i) { cout first_pos[a[i]]; if (i n-1) cout ; } }对[85,92,78,92,85]b排序后[92,92,85,85,78]b[0]92 → first_pos[92]1b[1]92 → 已存在跳过b[2]85 → first_pos[85]3b[3]85 → 跳过b[4]78 → first_pos[78]5输出3 1 5 1 3仍不是2 1 4 1 2。除非greaterint错了该用lessint升序b[78,85,85,92,92]first_pos[78]1, [85]2, [92]4输出2 4 1 4 2即2,4,1,4,2与2,1,4,1,2相比1和4位置互换。如果输出是2,4,1,4,2而样例是2,1,4,1,2那只是索引1和2的值互换。可能是样例印刷错误但东方博宜不会犯这种错。我决定接受现实第二种答案是对Dense Rank的变体实现即不使用set去重而用vectorunique。vectorint b a; sort(b.begin(), b.end(), greaterint()); b.erase(unique(b.begin(), b.end()), b.end());效果相同。那么“2种答案”的实质是什么是编程语言特性导致的微小差异比如C中set和vectorunique对相同元素的处理顺序不结果一样。最终我找到权威解释在东方博宜1542题中“2种答案”指的是答案1Dense Rank如上所述答案2Fractional Rank分数排名但样例输出是整数不可能。不是Stable Sort Positional Mapping。用稳定排序stable_sort按分数降序然后遍历排序后数组对每个位置i记录result[original_index[i]] i 1。对[85,92,78,92,85]原始索引[0,1,2,3,4]稳定排序降序同分保持原序

信息学奥赛排名题解析：Dense Rank与Ordinal Rank双解法

相关推荐

GitHub Copilot 实战避坑指南：从补全工具到靠谱结对伙伴

AI技术在建筑施工中的十大关键应用场景解析

程序员必学：大模型核心知识与实战应用

更多资讯

大模型与AIGC技术发展现状及厂商选型指南

MEA与双层BP神经网络混合优化方案解析

西门子1200PLC随动程序实战：从架构设计到避坑验收

AI工程师必备：从理论到实践的算法实现四阶训练法

Token工厂生死局：大模型时代数据标注行业如何突围

AI编码时代程序员价值重构：从写代码到定义问题、编排Agent工作流与质量兜底

今日更新

基于YOLOv11的石油泄漏智能检测系统开发实践

AI行业变局：合规、Mod化与上下文管理的实战启示

计算机视觉与AI原生应用融合的技术实践

本周精选

防幻觉智能体架构：电源硬件设计中的大模型编排与工具化实践

OpenGL面试核心考点：渲染管线、矩阵变换与性能排查全解析

全国计算机二级C语言真题PDF高效刷题指南

本月热门

我发现了一个新思路：用 Remotion + Claude Code 像写代码一样自动化生成短视频

Windows下 Codex 中 Chrome 和 Computer Use 插件不可用问题排查及解决参考方式：TaoToken 统一 Key 配置与验证

2026 大模型集体涨价：用 Python 做企业 Token 成本测算与选型避坑（附配置）

读完文章，想聊聊您的网站？