程序设计与算法第7讲OJ作业：结构体排序与二分查找避坑指南

很多人看到“程序设计与算法 | (14) Lecture(7) OJ作业”这个标题第一反应是不就一次上机作业嘛照着讲义写写提交就行。等真坐下来写才发现这一讲可能是很多人第一次在评测平台上连交五六次都过不了的地方。我复盘过周围同学第7讲前后的表现。前六讲的内容基本是变量、分支、循环、数组、函数虽然也会有语法错但多数问题停留在“写不写得出来”到了第7讲题目开始把结构体、排序、查找这些概念串在一起问题就变成了“就算写出来了评测机也不认”。这篇就围绕这一阶段最典型的几类作业题聊聊我当时是怎么拆题、怎么写、怎么排错的希望能给你省几次提交次数。1. 第7讲在课程里的位置第一次真正考“算法思路”1.1 前六讲没暴露的问题在这一讲集中爆发前六讲如果你跟着写过会发现绝大多数题目的解法是“翻译”出来的题目说输入一个数你就写 scanf说如果大于某个值你就写 if说循环累加你就写 for。语法知识点和题目要求一一对应代码只是对自然语言的直译。到第7讲情况变了。作业里的题目往往不直接告诉你“请定义一个结构体然后排序”而是给你一段描述比如“某门课有 n 个学生每个学生有姓名、学号和若干科成绩请按总分从高到低输出总分相同按学号从小到大”。你要做的第一件事不再是写代码而是把题目拆成三块用什么结构组织数据结构体字段怎么设计按什么规则比较两条记录排序比较函数怎么写输入输出要满足什么格式行末空格、换行、分数精度等。这个拆解过程才是“程序设计与算法”这门课真正开始的地方。之前做的是“编码”从第7讲开始做的是“解题”。很多同学在这个转变点上掉队不是因为代码能力不行而是因为还没有形成“先想清楚再动手”的肌肉记忆拿到题目直接开写写一半发现数据组织错了推倒重来一晚上就这么耗掉。1.2 本讲作业的常见题型画像虽然不同学校的OJ题库千差万别但第7讲这个位置作业题目的类型其实非常集中。我按这些年带过的学弟学妹遇到的题目列一个参考画像常见题型核心考点最容易挂掉的地方学生/商品/订单记录排序输出结构体、多关键字比较、排序稳定性同分规则漏掉或比较方向写反有序数组多次查询某个值二分查找、边界条件死循环、数组下标越界把若干个数按规则重新排列手写排序的循环边界冒泡内层循环多跑一轮在区间里找一个满足条件的值二分答案思想不会写合理性检查函数这一类作业的最终目标是让你建立一种思维习惯任何一条记录都能抽象成一个结构体任何一组规则都能写成独立的比较函数任何一次查找都要先想数据规模再决定用线性还是二分。如果你能把这三句话变成条件反射这一讲就算真正过关了。2. 结构体排序写对比较规则比背排序代码更要紧2.1 先定数据结构字段怎么设计直接影响后面好不好写结构体排序题第一步是确定结构体的字段。别小看这个动作我见过太多人因为字段设计不合理后面写出一堆别扭代码。以最常见的成绩排序为例题目通常给出姓名、学号、三科成绩。建议这样组织struct Stu { string id; // 学号注意可能带前导0必须用字符串存储 string name; // 姓名如果题目说不含空格用 string 或 char[] 都行 int score[3]; // 三科成绩 int total; // 总分也可以在读入后单独计算 };有两个细节值得强调学号一定用字符串存不要用 int。很多题目的学号长这样“001”“002”……如果读成 int排序时 2 会排在 10 前面而且输出时前导 0 直接丢失。这种错误非常隐蔽本地样例往往看不出问题一提交就是 Wrong Answer。哪怕学号全是纯数字只要题目没说“保证学号是正整数且无前导零”就默认它是字符串。总分在读入时就算好不要在排序过程中临时算。有人喜欢把排序规则写成“比较时现算总分”这样不是不行但每次比较都要重复循环三科成绩数据量一大就多出很多无谓的开销。更好的做法是读入一条记录后立刻把总分存进结构体后面所有比较都只访问这个字段。2.2 比较规则怎么写逻辑集中符号看清楚比较是结构体排序里最关键的环节。新手最常见的错误是在主函数里写一长串 if-else 循环比较而更稳的做法是写成一个独立的比较函数比如bool cmp(const Stu a, const Stu b) { if (a.total ! b.total) return a.total b.total; // 总分降序 return a.id b.id; // 同分按学号升序 }然后一句话调用排序sort(stu, stu n, cmp);这个函数本身不复杂但很多人会在符号上翻车。我建议你在写完比较规则后用一句话把它念出来“总分高的排前面总分一样学号小的排前面。”然后对照代码检查第一行是大于号还是小于号第二行是小于号还是大于号。念一遍比反复盯着屏幕看更有效。另一个常见的认知误区是比较函数必须返回严格弱序也就是“小于”关系要自洽。如果你写return a.total b.total;在 sort 里可能会造成未定义行为结果不确定。比较函数里只写“谁应该排在谁前面”的严格规则不要带等号。2.3 手写排序的三个边界错误有些作业明确规定“不许用库函数排序”要求自己实现冒泡或选择排序。这一点本身不难但手写排序出错率反而比调用库函数高因为边界条件太容易写错。以冒泡排序为例最典型的错误长这样for (int i 0; i n - 1; i) { for (int j 0; j n - i; j) { // 错误应该是 j n - i - 1 if (a[j] a[j 1]) { swap(a[j], a[j 1]); } } }当j n - i - 1时j 1 n - i如果内层循环没有减 1最后一次循环会访问到a[n - i]。若i 0就是访问a[n]直接越界。更麻烦的是如果数组后面恰好还有一块合法内存程序不一定会崩溃只会出现莫名其妙的排序结果——这种问题非常难查。我自己的经验是手写排序前先在纸上用小规模数据推一遍循环过程。比如 n3写出每一轮 i 和 j 的变化确认每轮能确定哪个位置上的元素。这个推演过程只需要两分钟但能省下一小时调试时间。还有个容易忽略的点如果你手写的是选择排序而题目要求“总分相同按学号升序”那么比较时遇到总分相等的两条记录不应该交换。你写的交换条件是“前者比后者差才交换”而不是“前者不比后者好就交换”。这个细微差别决定了稳定性而稳定性正是这道题的隐藏考点。2.4 库函数怎么选sort、qsort 与 stable_sort如果老师允许用库函数我强烈建议优先用 C 的sort而不是 C 语言的qsort。qsort的回调函数要写const void*指针加类型强转代码丑且容易出错sort配合比较函数干净得多。但有一个场景要特别注意题目明确要求“当关键字段相同时保持输入顺序”。这时候sort不一定能保证稳定应该改用stable_sort。虽然第7讲的多数题目会额外给出学号之类的第二关键字但万一遇到这种隐藏要求用stable_sort是最稳妥的。另外注意调用方式别搞混对结构体数组排序是sort(stu, stu n, cmp)对 vector 排序是sort(v.begin(), v.end(), cmp)。这个差别很小但我见过不少人在两个写法之间来回切换时把迭代器写成了指针。统一一种容器风格能减少这类无谓错误。3. 二分查找从“找值”到“找答案”的跃迁3.1 什么时候该想到用二分第7讲的作业里几乎必有一道二分查找题但很多人一看到“查找”就直接暴力线性扫。如果数据规模只有几千线性扫确实没问题可一旦题目给的 n 和 m 都是 10^5 级别线性扫描 O(n·m) 就是 10^10 次操作评测机怎么都不可能让你过。我一般会用一句话判断如果题目里出现“有序”“多次查询”“答案在某个区间内”这些词并且数据规模超过 10^5就要考虑二分。这个判断不需要精确只要你有这个意识就能避免大部分超时。常见的入门题是这样描述的给定一个升序数组进行 m 次查询每次给一个数字 x输出 x 在数组中的位置下标从 0 开始若不存在则输出 -1。如果数组长度是 10^5查询次数也是 10^5线性查找必然超时而二分查找每次 O(log n)整体只有约 1.7×10^6 次操作是量级上的差距。3.2 边界问题死循环到底是怎么来的二分查找的核心不难难的是边界条件。很多人背模板但背完换一道题就死循环。我复盘过自己早期的错误发现死循环几乎都来自同一个原因更新区间时没有让搜索区间真正缩小。看这个错误版本int l 0, r n - 1; while (l r) { int mid (l r) / 2; if (check(mid)) { l mid; // 危险如果 mid l死循环 } else { r mid; } }当l和r只差 1 时比如l 3, r 4mid (3 4) / 2 3。如果此时check(3)为真执行l mid结果是l仍然是 3区间没有任何变化下一轮还是同样的mid——死循环。解决办法是记住一个口诀如果更新方式是“左边界右移”l midmid 计算时要向上取整如果是“右边界左移”r midmid 计算时向下取整即可。也就是说int mid (l r 1) / 2; // 当你想执行 l mid int mid (l r) / 2; // 当你想执行 r mid上取整保证了当区间只有两个元素时mid 会取到右边的那个这样l mid之后区间确实会向左收缩一个位置不会陷入自我重复。更稳妥的写法是直接采用“闭区间 我们最终要在外部维护答案”的方案int l 0, r n - 1, ans -1; while (l r) { int mid (l r) / 2; if (a[mid] x) { // 比如找第一个 x 的位置 ans mid; r mid - 1; } else { l mid 1; } }这种写法更新时都是mid ± 1区间必然缩小不需要纠结上取整下取整对初学者最友好。我后来写二分基本都优先用这个模式。3.3 二分答案本阶段最容易“超纲”的送分题第7讲作业里还有一种题表面看起来和二分没关系比如“有 n 根长度不一的木料要切出 k 段长度相同的成品每段最长能切多少”。直接枚举长度是不现实的——如果最长那根有 10^9枚举到天荒地老。正确思路是反向思考不问你“某段长度能不能切”而问“给定一个长度 L能不能切出至少 k 段”。这个判断函数极简单bool check(int L) { long long cnt 0; for (int i 0; i n; i) { cnt len[i] / L; // 每根木料能切出几段 L } return cnt k; }然后对答案空间做二分int l 1, r maxLen, ans 0; while (l r) { int mid (l r) / 2; if (check(mid)) { ans mid; // mid 可行试试更大的长度 l mid 1; } else { r mid - 1; // mid 不可行只能缩小 } }这种做法叫“二分答案”第7讲如果出现其实是给后面做铺垫。它把“求最值”转化成“对一个可行性函数做二分”思想一旦接受很多看似复杂的题会变得很机械化。你去翻后续讲义会发现“最小值最大”“最大值最小”这类模型本质都是这个思路的变体。4. 一次OJ作业的完整排错复盘从样例通过到拿到AC前面讲了一堆理论下面说一次真实作业的完整复盘。题目我按常见配置简化过就叫它“排榜题”吧有 n 个学生的姓名、学号、三科成绩按总分降序输出姓名和学号总分相同的按学号升序n 最大 10^5。限制 1 秒内存 128MB。4.1 第一版本地样例秒过交上去全是 Wrong Answer我第一次写这道题时想的很简单直接在主函数里用 sort比较函数如下bool cmp(const Stu a, const Stu b) { return a.total b.total; // 问题漏了同分规则 }本地样例只有两组数据一组总分都不同一组有一个同分但恰好按输入顺序排列结果样例全过。提交后大面积 WA。这个阶段的常见心理是“样例都过了怎么会错”对吧。实际上评测数据里专门有那种同分且学号顺序和预期相反的情况我的比较函数在总分相等时返回 falsesort 就会认为两个记录“相等”顺序由排序算法内部决定完全不可控。这正好是题目想考核的隐藏点。4.2 第二版补了同分规则却从 WA 变成了 TLE我改完比较函数后bool cmp(const Stu a, const Stu b) { if (a.total ! b.total) return a.total b.total; return a.id b.id; }逻辑看起来没问题结果一提交判题结果变成了 Time Limit Exceeded。本地跑 10^4 条数据很快但评测机上 10^5 条数据就慢得多了。这时候很多人会以为是排序太慢于是手写快排、换堆排折腾半天。其实问题可能在输入输出上。我当时用的全是cin和cout而且没有关闭输入输出同步在 10^5 级别的数据下cin的缓冲区开销会放大很多倍。解法很简单在 main 开头加两行ios::sync_with_stdio(false); cin.tie(0);或者直接改成scanf/printf。加上之后本地用 5×10^5 条随机数据试了一下运行时间从接近 2 秒降到 0.4 秒左右完全是两种体验。这个坑很典型题目给的数据规模往往刚好卡在“cin 默认模式会超时、但关同步后能过”的区间。如果遇到 TLE先别急着改算法先确认是不是输入输出拖了后腿。4.3 排错方法论永远先造最小数据再谈优化回头看这三至四次的提交我最想分享的经验是拿到 WA 之后第一件事不是盯着代码猜而是造一组你能人工算出答案的最少数据把程序跑一遍看输出和预期差在哪。比如这次我可以构造3 A01 Alice 90 80 70 // 总分240 A03 Bob 85 85 70 // 总分240 A02 Carol 80 80 80 // 总分240三条记录总分全相同就靠学号排序预期输出顺序是 A01、A02、A03。如果程序输出不是这个顺序说明比较规则有问题如果输出是对的再逐渐增加数据变体学号前导零、姓名字符串、总分极大值、只有一条数据、所有数据总分和学号都相同。这一套“最小测试矩阵”走下来大部分逻辑错误都能暴露。我把常见的判题结果和排查优先级整理成一个表判题结果含义优先排查方向Compile Error编译错误变量名、头文件、语法拼写Runtime Error运行时错误数组越界、空指针、除以零Wrong Answer答案错误比较规则、输出格式、边界值Time Limit Exceeded超时输入输出优化、算法复杂度、死循环Presentation Error格式错误行末空格、换行、输出顺序Accepted通过恭喜进入下一题还有一个隐藏问题值得单独说如果累加的不是三科成绩而是几十次平时作业总分可能超过 int 的稳定安全区这时候要用 long long。很多题目不会明说成绩范围但如果你预估最大值超过 2^31-1 就果断换 long long。这个细节等到后面数据范围更大的题目里会变成全校范围的 WA 重灾区。5. 往深一步这一讲可以为后面的算法学习铺哪些路5.1 从排序到归并逆序对值得做一次如果第7讲的作业你都能 AC我建议你做一道提升题求一个长度为 n 的数组的逆序对数量。逆序对的定义是i j且a[i] a[j]的数对数量。这道题和本讲有什么关系冒泡排序的交换次数本质上就是逆序对数量。如果你手写过冒泡会发现每次交换都在消除一个逆序对所以求逆序对数量就是另一种形式的排序问题。暴力双重循环能过小数据但 10^5 级别必须上归并排序。归并排序在合并两个有序区间时如果右边区间的元素a[j]小于左边区间的某个元素a[i]那么左区间从i到mid的所有元素都和a[j]构成逆序对一次累加res mid - i 1;这一行是整个算法的精髓。做这道题能帮你同时复习“分治思想”和“排序的本质”比盲目刷十道简单排序题的收获大得多。5.2 从二分查找值到二分判定问题第7讲的二分作业多数是让你“在数组里找某个值”这是二分最基础的应用。再往后走二分真正的威力体现在“对答案做判定”。你只需要把题目中要求的“最大值最小化”或“最小值最大化”翻译成“给定一个答案能否满足条件”剩下的就是模板化的二分过程。这种模型在后续会反复出现比如规划类题目里的可行性检查、资源分配题的贪心判定等。我的建议是本阶段不要把二分当成背代码题而是每次做题时都刻意问自己一句——“如果我已经知道答案能不能快速验证它”一旦有这个思维习惯后面遇到新题就会自然往二分答案上靠。5.3 课后落地动作三条我用过的执行清单最后分享我自己在这一讲结束时固定执行的三个动作算是给读者一个可以直接照做的版本第一讲义里的例题不看提示独立 AC 一遍。听懂了和写出来了是两回事能独立 AC 才说明知识点真正进脑子。如果卡了超过 20 分钟可以看提示但看完必须把代码删掉隔一天再独立写一遍。第二为每次 WA 写一条错误记录。不用复杂就在本地代码文件开头注释一行比如“2024-xx-xx比较函数漏了同分规则”。坚持几周你会发现同一个坑基本不会踩第二次。这件事比多刷十道题还管用。第三按“基础 延伸”的节奏刷题。本讲作业本身是基础我会再找一个同层次题巩固比如另一道结构体排序题再挑一道延伸题比如逆序对或二分答案。不要一上来就啃难题这个阶段的核心是把已经会的题写对、写稳而不是追求题目难度。说实话到第7讲为止大部分人的差距还不是天赋而是能不能静下心来把代码里的每一个小毛病找出来。我见过很多同学在拿到 AC 之后还会翻回自己 WA 的版本把错误原因写在注释里这种复盘习惯长期积累下来比单纯刷题量管用得多。如果你也想在这门课上走得稳一点不妨从这次作业开始给每次错误留一条记录。