★ FEATURED ARTICLE 前阵子帮一位朋友复盘认证题库里编号D35的这道第二题复盘完觉得非常值得写一篇。原因是这类题太有代表性了表面是一个排序题实际考的是结构体设计、多关键字排序和罚时规则理解。我见过不少人第一题秒过第二题卡了半小时最后排名就差这两分真的很可惜。D35的题面原型是模拟一场比赛的最终榜单。输入里给N支队伍、M道题、K条提交记录每条记录有队伍编号、题号、提交时间和评测结果AC或非AC。你需要输出所有队伍的排名排序规则依次是AC题数降序、总用时升序、队伍编号升序。总用时计算方式是每道AC题目的首次AC时间加上该题AC之前所有错误提交次数乘以20分钟。未AC的题不计算罚时AC之后继续提交也不再影响结果。很多同学看到这个题就觉得“这不就是个sort吗”结果一写就漏条件。所以我把做题的完整思路拆开写出来把每一条规则的代码落地方式、常踩的坑、还有考场上的处理节奏都过一遍。无论你是准备认证、准备复试上机还是刚开始打算法竞赛这篇应该都能帮上忙。1. 题目拆解D35 在考什么为什么第二题经常翻车1.1 题面原型一眼看穿排名规则先把这个题的题面补完整因为很多人的WA都是没把“规则”当数据读。D35的完整规则可以概括成这么几条有N支队伍编号1到N有M道题编号1到M有K条提交记录。每条提交记录包含队伍编号id、题目编号p、提交时间t分钟、评测结果resAC表示通过其它表示未通过。排名的第一关键字是AC题数越多越靠前。第二关键字是总用时越少越靠前。总用时等于所有已AC题目各自的“首次AC时间 该题AC之前所有非AC提交次数 × 20分钟”之和。第三关键字是队伍编号编号小者靠前。已AC的题目如果之后再有提交无论结果如何都不再计入任何统计。未AC的题目它产生的错误提交次数不进入总用时。这类规则在竞赛里叫“ACM/ICPC赛制排名”。你可能在不少OJ的Contest榜单里见过类似东西。它本质上就是一个自定义排序加一点模拟细节没有任何高深算法。1.2 算法思维这不是难题是细节题这道题放到第二题的位置我觉得很有深意。它筛的其实不是算法而是“能不能把中文规则准确翻译成代码”。举个例子“AC之后继续提交不管结果如何都不影响”这句话很多人写着写着就忘了。他们可能在process函数里先判断结果是否为AC再去判断这道题是否已经AC。如果同一道题AC后又来了一次AC提交程序就会把solved和penalty重复累加一次。这就是典型的“规则理解不到位导致的WA”。再比如“未AC的题目不计算罚时”这句话。很多人会在比较总用时的时候把所有错误提交次数乘20加进去甚至把没AC的题的提交时间也加进去。这些错误在样例数据上往往看不出来因为样例通常给得很仁慈但一到评测数据就现出原形。所以我一直强调做这类题的第一步不是写代码而是把规则在草稿纸上重新写一遍最好用“如果…那么…”的句式。等规则清晰了代码只是按翻译的产物。1.3 复杂度估算与方案选型接下来看一下数据范围和方案。D35的数据量一般是N不超过10000M在10到20之间K在100000以内。这个量级下算法选择非常明确用结构体数组存队伍信息每读一条记录就O(1)更新对应队伍的状态。所有记录处理完之后用sort对队伍数组排序排序复杂度O(N log N)。最后线性输出。总时间复杂度O(K N log N)空间复杂度O(N × M)。这里N取10000、M取20时数组占用大约是10000 × 20 ×1个bool 2个int的大小撑死几MB完全不用担心。有些同学一看到“排名”就想到平衡树、优先队列其实完全用不上。关键原因是题目要的是“最终榜单”所有提交结束之后才排名。如果题面改成边提交边显示实时榜单那才需要在线维护排名但D35不是这种题。选型前先想清楚要的是静态结果还是动态结果能省很多不必要的工作。2. 数据建模把中文规则翻译成代码结构2.1 队伍信息怎么存写代码之前先在草稿纸上设计结构体。我习惯这样设计const int MAXN 10010; const int MAXM 15; struct Team { int id; // 队伍编号 int solved; // AC题数 int penalty; // 总用时 bool ac[MAXM]; // 每道题是否已经AC int waCnt[MAXM]; // 每道题AC之前的错误提交次数 }; Team teams[MAXN];为什么每个字段都需要这里简单拆一下id用于排序的第三关键字也是最终输出的队伍编号。solved是第一关键字记录AC题数。penalty是第二关键字记录总用时。ac数组用来判断某道题是否已经过了避免重复累加。waCnt数组用来记录AC之前这道题错了几次计算罚时的时候要乘20。有同学可能会问要不要把“首次AC时间”存下来如果只是求总用时其实不用单独存因为累加penalty的时候已经把时间算进去了。但如果你后面想扩展输出“某题最快AC时间”之类的字段存一下也行。我在写D35基础版的时候没有存保持结构干净。初始化也很关键尤其是数组下标从1开始用的情况。直接在main里对1到N循环初始化void init(int n) { for (int i 1; i n; i) { teams[i].id i; teams[i].solved 0; teams[i].penalty 0; memset(teams[i].ac, 0, sizeof(teams[i].ac)); memset(teams[i].waCnt, 0, sizeof(teams[i].waCnt)); } }注意memset只处理ac和waCnt数组不要顺手把id也清了。很多人习惯对整个结构体memset那会把id也变成0排序时第三关键字就乱了。2.2 提交记录怎么处理处理提交记录是整个题的核心。推荐写一个独立的process函数主循环里每读一条记录就调用一次void process(int id, int p, int t, const string res) { if (teams[id].ac[p]) { return; // 已经AC的题之后的提交全部忽略 } if (res AC) { teams[id].ac[p] true; teams[id].solved; teams[id].penalty t teams[id].waCnt[p] * 20; } else { teams[id].waCnt[p]; } }这个函数的逻辑顺序很重要。第一步先判断“这题是否已经AC”是的话直接return。不要先判断结果是否为AC那样会出问题。举个例子某队第1题已经AC之后又来了一条第1题WA记录。如果先判断res AC再判断ac[p]那么在WA分支里依然会把waCnt[1]加1这就污染了罚时数据。如果这道题后面没有再AC可能暂时不影响但如果你的代码逻辑里还有二次计算就会出错。正确的做法是把ac[p]当成总开关一旦AC后面所有提交都进不来。还有一点处理res字符串时直接比较res AC是可行的。但有些竞赛环境里评测结果还可能写成AC以外的字符串比如WA、TLE、RE、CE、PE。只要不是AC都算错误提交所以用if (res AC)判断就够了不需要把所有错误类型都列出来。2.3 排序比较函数为什么必须严格弱序C的sort要求比较函数满足“严格弱序”。简单说就是不能出现a b和b a同时为真的情况也不能出现逻辑矛盾。如果比较函数写得不严谨sort的行为是未定义的可能输出顺序和你预期完全不一样。D35的比较函数按题意写就可以了bool cmp(const Team a, const Team b) { if (a.solved ! b.solved) return a.solved b.solved; if (a.penalty ! b.penalty) return a.penalty b.penalty; return a.id b.id; }注意三条规则都要写全。AC数不同比AC数AC数相同比罚时罚时也相同比编号。如果漏掉最后的a.id b.id当两支队伍AC数和罚时完全一样时它们的相对顺序是不确定的。对某些OJ来说两个相同元素顺序不定输出就会不稳定很可能被判WA。另外sort比较函数里的参数建议用const引用避免无意义的拷贝。虽然结构体不大但竞赛养成的习惯还是尽量写const Team a。3. 完整实现一版能直接提交的 C 代码3.1 核心代码与逐段解释把前面几块拼起来就是一版可以直接提交的代码。我按“读入-处理-排序-输出”四段来讲。#include bits/stdc.h using namespace std; const int MAXN 10010; const int MAXM 15; struct Team { int id; int solved; int penalty; bool ac[MAXM]; int waCnt[MAXM]; }; Team teams[MAXN]; void init(int n) { for (int i 1; i n; i) { teams[i].id i; teams[i].solved 0; teams[i].penalty 0; memset(teams[i].ac, 0, sizeof(teams[i].ac)); memset(teams[i].waCnt, 0, sizeof(teams[i].waCnt)); } } void process(int id, int p, int t, const string res) { if (teams[id].ac[p]) return; if (res AC) { teams[id].ac[p] true; teams[id].solved; teams[id].penalty t teams[id].waCnt[p] * 20; } else { teams[id].waCnt[p]; } } bool cmp(const Team a, const Team b) { if (a.solved ! b.solved) return a.solved b.solved; if (a.penalty ! b.penalty) return a.penalty b.penalty; return a.id b.id; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n, m, k; cin n m k; init(n); for (int i 0; i k; i) { int id, p, t; string res; cin id p t res; process(id, p, t, res); } sort(teams 1, teams n 1, cmp); for (int i 1; i n; i) { cout teams[i].id teams[i].solved teams[i].penalty \n; } return 0; }代码里有两个容易被忽略但很重要的点第一sort(teams 1, teams n 1, cmp)表示对下标1到n的元素排序因为开数组是从1开始用的。如果你用sort(teams, teams n 1, cmp)会把teams[0]也排进去而teams[0]是未初始化的一堆脏数据排序结果直接错。第二输出用\n而不是endl。endl除了换行还会强制刷新输出缓冲区在提交记录达到10万级别时频繁刷新会让程序慢一个量级。这是很多人在大数据点TLE的隐藏原因。3.2 样例推演自己动手验一遍光说理论不够我来构造一个小样例手工推演一遍。设N3M2K6提交记录如下队伍题号时间结果1110WA1115AC215AC2220WA2230AC315AC逐步推演1号队第1题先WA一次再AC该题罚时151×2035AC数1总用时35。2号队第1题AC罚时5AC数1。第2题先WA再AC罚时301×2050。总用时55055AC数2。3号队第1题AC罚时5AC数1。排序后第一名2号队AC数2总用时55。第二名3号队AC数1总用时5。第三名1号队AC数1总用时35。程序输出应为2 2 55 3 1 5 1 1 35这里有一个特别容易看走眼的地方1号队和3号队AC数都是1但1号队总用时353号队总用时5所以3号队排前面。这正好验证了“总用时少者靠前”不是总提交时间少者靠前而是罚时规则下算出来的总分。如果谁把1号队的10分钟WA时间单拎出来加进总用时就会算成45排序就错了。3.3 输出细节与常见变体输出的时候要看清楚题面是要求输出所有N支队伍还是只输出有提交记录或AC的队伍。D35原题里要求输出所有队伍所以你直接排完输出整个数组即可。有些变体题只输出“有提交记录”的队伍那你就需要加一个标记比如在process里置hasSubmit[id] true最后只遍历有标记的队伍。输出格式也要留意很多题要求每行“队伍编号 AC题数 总用时”中间用空格隔开。行尾不能有额外空格。我这里用cout id solved penalty \n就是标准格式。如果题目要求按排名顺序输出排名序号比如“第几名 队伍编号”那你就在输出循环里用一个计数器rank每次输出后自增。D35基础版不要求但扩展时很容易加上。4. 我踩过的坑WA、TLE 与调试技巧4.1 最常见的 WA 原因我把这道题最常见的WA原因整理成一个表你们可以直接对照错误类型错误写法正确思路已AC后继续处理先判结果再判AC状态先判断ac[p]已AC直接return罚时统计错误未AC题的错误提交也乘20加进penalty只在AC时累加错误罚时比较函数不完整只比较solved和penalty漏了id三个关键字按规则全部写全输出顺序不稳定随意用sort且cmp没有严格弱序保证cmp对相等情况有明确顺序数组大小不足MAXM只开到10但M可能12把M上限2再开数组初始化遗漏结构体里ac数组是全局的残留值用memset对所有队伍初始化前两条是典型的“逻辑顺序问题”后几条偏工程细节。每次WA的时候我都建议先按这个表逐项自查一遍比盯着屏幕发呆有效得多。4.2 运行超时和效率问题D35的运算量本身不大理论上不可能TLE。如果超时了十有八九是IO或者排序比较函数出了效率问题。第一个常见问题是cin没有关同步。C的cin默认会和C标准IO同步导致输入变慢。在main开头加这两行ios::sync_with_stdio(false); cin.tie(nullptr);输入量是10万行的时候这两行能明显提速。如果你不想用cin也可以用scanf但要注意类型匹配。第二个常见问题是输出的时候用了endl。前面说过endl会刷新缓冲区。一次刷新可能不明显但输出N行时每行刷一次累计开销就很可观。改成\n即可。第三个问题比较隐蔽有些同学把所有提交记录用一个vector存下来最后再统一处理。这本身不是不行但当K很大时vector的扩容和内存占用是多余的。D35根本不需要存历史记录边读边算就够了。4.3 高效调试三板斧我调试这类题目一般用三个办法效率很高。第一招小样例手算。手动构造2到3个队伍、1到2道题、4到6条记录的小样例先自己算出预期结果再用程序跑一遍对比。上面的样例推演就是这么来的。第二招随机对拍。写一个暴力版怎么简单怎么来和一个优化版随机生成数据比较输出。很多WA在随机数据下会快速暴露。用Python写个随机数据生成器跑一百组几秒钟就能发现问题。第三招关键点打印。在process函数里临时加一行输出处理完后的solved和penalty。比如打印1号队第1题AC后 solved1 penalty35。这一步能帮你确认是更新逻辑错了还是排序逻辑错了。提交前把这行注释掉就行。5. 从 D35 延伸出去的通用解题套路5.1 第二题高频考点清单第二题在认证里其实有比较固定的考法。我给自己整理过一个清单刷题时对着清单找题练排序模拟成绩排名、商品榜单、日志统计、比赛排行榜。简单数据结构栈模拟括号、队列模拟约瑟夫环、堆求TopK。字符串处理单词计数、字符串去重、进制转换。数学模拟日期计算、矩阵旋转、分数运算。D35属于第一类“排序模拟”。这类题的关键是先把规则写清楚再设计结构体最后写比较函数。只要练熟三到五道同类题遇到变体基本都能很快写出来。我还想多说一句第二题不一定每次都是排行榜但“给一堆记录按规则排序输出”这种出题模式特别常见。你只要掌握“结构体sortcmp”的套路就能覆盖很大一片题目。5.2 考场上怎么分配时间和检查步骤我在考场上给自己定的节奏是这样的前5分钟读题把规则用自己的话复述一遍。接下来5到10分钟设计结构体和状态更新逻辑在草稿纸上画一下字段。然后写代码边写边想着边界条件。写完先拿样例跑再自己构造一个极端小数据。最后提交前花30秒做三道检查罚时是否只在AC时累加排序是否包含全部关键字输出格式和题面是否一致。这三道检查基本覆盖了这类题90%的WA原因。如果你做的是排行榜模拟题把这套流程走完心里就会很有底。有些同学喜欢一上来就写代码写到一半发现设计不对推倒重来反而更慢。先把结构和规则理顺代码写得快错得也少。最后分享一个小习惯我个人做这类题有个偏好不管题面允不允许我都不用Python作为提交主力。不是Python不能写而是同样的逻辑在大量输入下C的读写和sort更稳。Python比较适合用来写对拍和生成随机数据但提交主力用C能省很多心。还有一个细节想提醒你如果你在比赛现场遇到一道排行榜题WA但又找不到原因试着把样例简化成只有一条提交记录比如“1 1 0 AC”看输出是不是“1 1 0”。如果不是说明基本逻辑就有问题如果是再逐步加数据。这种方法比自己空想要快得多。D35这种题本质就是细心活。规则读透、结构设计对、比较函数写全AC就是水到渠成的事。
阅读完成 · 觉得有帮助？
