企业官网建设流程全解析

前阵子帮一位朋友复盘认证题库里编号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（分钟）、评测结果res（AC表示通过，其它表示未通过）。
• 排名的第一关键字是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不超过10000，M在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 样例推演：自己动手验一遍

光说理论不够，我来构造一个小样例手工推演一遍。设N=3，M=2，K=6，提交记录如下：

逐步推演：

• 1号队第1题：先WA一次，再AC，该题罚时=15+1×20=35，AC数=1，总用时=35。
• 2号队第1题：AC，罚时=5，AC数=1。第2题先WA再AC，罚时=30+1×20=50。总用时=5+50=55，AC数=2。
• 3号队第1题：AC，罚时=5，AC数=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号队总用时35，3号队总用时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原因整理成一个表，你们可以直接对照：

前两条是典型的“逻辑顺序问题”，后几条偏工程细节。每次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后 solved=1 penalty=35。这一步能帮你确认是更新逻辑错了，还是排序逻辑错了。提交前把这行注释掉就行。

5. 从 D35 延伸出去的通用解题套路

5.1 第二题高频考点清单

第二题在认证里其实有比较固定的考法。我给自己整理过一个清单，刷题时对着清单找题练：

• 排序+模拟：成绩排名、商品榜单、日志统计、比赛排行榜。
• 简单数据结构：栈模拟括号、队列模拟约瑟夫环、堆求TopK。
• 字符串处理：单词计数、字符串去重、进制转换。
• 数学模拟：日期计算、矩阵旋转、分数运算。

D35属于第一类“排序+模拟”。这类题的关键是：先把规则写清楚，再设计结构体，最后写比较函数。只要练熟三到五道同类题，遇到变体基本都能很快写出来。

我还想多说一句：第二题不一定每次都是排行榜，但“给一堆记录，按规则排序输出”这种出题模式特别常见。你只要掌握“结构体+sort+cmp”的套路，就能覆盖很大一片题目。

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就是水到渠成的事。