每年校招季技术岗笔试都是第一道硬门槛。美团近两年的校招技术笔试分多场进行题目难度分布相对稳定第三场的题型组合在“思维复杂度”和“编码量”之间取了一个比较合适的中间值——比第一场更偏算法设计又不像第四第五场那样动不动就上树套树。如果你正在准备2023届或往后年份的美团笔试那这场题值得拿来当标杆刷。先说下这套题给人的整体印象第三场一共四道编程题覆盖了贪心、动态规划、二分答案、差分数组这几个高频考点没有特别偏门的AC自动机或后缀数组这种冷门结构但每一道题都藏了一个“如果不绕一下就会被卡住”的细节。整场限时大概两小时四道题全部AC的人不多但AC两道以上是多数人的目标线。这篇文章不打算复述原题面而是把我对这套题的技术点拆解、代码实现思路、以及考场上的实际取舍记录下来给后面要参加校招笔试的朋友一个可复用的解题框架。1. 整体设计与考点拆解这四道题到底在考什么1.1 核心考点分布从技术点上归纳2023校招技术第3场的题目设计有很明显的“分层筛选”意图。先看我整理出的考点对应表题号核心考点数据规模特征隐含的知识点T1贪心 排序元素个数在10^5级别排序策略的证明能力T2前缀和 / 差分区间操作在10^5级别离线处理思想T3二分答案 贪心校验答案范围大校验过程非线性单调性分析能力T4动态规划 状态压缩优化状态维度多需滚动数组状态转移优化经验这个分布和牛客网上大部分同学反馈的“第二题和第三题区分度最大”是吻合的。第一题基本属于送分题但有个小坑第二题如果想不到差分数组用线段树也能做但编码复杂度直接翻倍第三题是全场分水岭能快速识别出“这是一个二分答案模型”的人可以省下大量时间第四题对思维能力要求最高属于压轴题定位。1.2 为什么这样设计从题目反推美团的筛选逻辑美团技术笔试的题目风格可以提炼出一个很明确的信号这家公司不追求“偏难怪”而是追求“在有限时间内考察候选人能不能把常见算法模型识别出来并快速实现”。第三场尤其明显。举个例子第二题区间操作题如果直接模拟每个操作复杂度是O(n×m)数据一大就超时。有些人会条件反射地想线段树、树状数组这在ACM竞赛里是标准解法但在校招笔试里反而落了下乘。出题人希望你想到“差分数组一次前缀和”这个更简单的工具。这种设计思路说明美团更看重的是你“会不会把问题化简”而不是“会不会搬高级数据结构”。我在实际刷题时也有一个明显的感受美团题目的数据范围设置得非常精准它就是要让你必须用某个特定复杂度的算法才能过不是单纯做仁慈的阈值设计。所以准备美团笔试千万不要一上来就抱着《算法竞赛进阶指南》啃而是先把基础算法模型的适用条件练熟。贪心什么时候能用、二分答案的单调性怎么证明、差分数组在什么场景下可以替代线段树这些问题才是第三场真正想考的东西。2. 核心细节解析两道高区分度题目的思路重构2.1 区间操作问题从暴力到差分的思维跳跃第三场的第二题我印象里是一道典型的区间更新问题。题目大致场景是给定一个长度为n的数组初始全为0然后有m次操作每次把某个区间[l, r]内的所有数加上一个固定值v最后要求输出整个数组的最终值。数据范围是n和m都达到10^5级别。如果你没有接触过差分数组第一反应一定是写一个for循环从l到r逐个加v。这在小数据时完全没问题但10^5的n和10^5的m相乘就是10^10稳超时间限制。这时候需要转换思路区间操作的批量处理应该用“记录变化”而不是“执行变化”。差分数组的核心思想是我们不直接维护数组的每个值而是维护相邻两个值之间的差值。定义差分数组d[i] a[i] - a[i-1]约定a[0]0。对区间[l, r]加v在差分数组上只需要做两次操作d[l] vd[r1] - v。全部操作记录完之后只需要对d做一次前缀和就能还原出最终的a数组。这里有一个初学者很容易想不明白的点为什么d[r1]要减去v原因是前缀和还原时超过r位置的那个“增量”必须被抵消掉否则r1之后的所有元素都会被错误地加上v。用生活化的类比来说这就像你在打卡记录上标记从第l天开始每天多写v行代码到第r天截止那第r1天开始就要把这个增量取消掉。差分数组的d[r1] - v就是那个“取消标记”。下面是这题的标准实现用C写因为笔试环境里C的IO速度最有保障#include bits/stdc.h using namespace std; int main() { int n, m; cin n m; vectorlong long diff(n 2, 0); for (int i 0; i m; i) { int l, r; long long v; cin l r v; diff[l] v; diff[r 1] - v; } vectorlong long ans(n 1, 0); for (int i 1; i n; i) { ans[i] ans[i - 1] diff[i]; } for (int i 1; i n; i) { cout ans[i] \n[i n]; } return 0; }这段代码里我用了long long而不是int这是一个很重要的细节。假如n10^5m10^5每次v10^9那累加值可能到10^14远超int范围。笔试里的数据范围经常是“不会明说但会卡你”的地方变量类型选错了哪怕算法对最后也可能WA几个数据点。这个教训是我在牛客网刷题时踩过的真实坑。2.2 二分答案应用题如何识别单调性并快速建模第三题是整个第三场区分度最大的题。题目背景我记得是关于资源分配或任务调度的给定一系列任务和可用时间要求找到某个“最大值的最小值”或“最小值中的最大值”。这类题目最关键的识别特征就是题面里会出现“最大化最小值”或“最小化最大值”这种说法或者可以用“如果答案不超过x是否可行”来验证。二分答案的思维模型是这样的我先猜一个答案mid然后设计一个check(mid)函数判断在mid这个答案下方案是否可行。如果mid可行说明答案可以更小或更大我就缩小搜索范围如果mid不可行就反向调整。整个过程依赖一个核心性质——答案的单调性如果x可行那么所有大于x或小于x的某些值也一定可行这才使得二分成立。用一个具体场景来举例假设这题是这样有n个任务每个任务需要耗时t[i]m台机器可以并行处理任务每台机器同一时间只能处理一个任务问完成所有任务的最短时间。这题的check函数就可以这么设计给定一个时间上限T判断m台机器在时间T内能否完成所有任务。贪心地看把任务按耗时从大到小排序用优先队列维护每一台机器的累计空闲时间模拟任务分配。如果所有任务都能在时间T内塞进去那么T可行可以尝试更小的时间。这个check函数的时间复杂度是O(n log m)在二分外面套一层log n的复杂度总体是O(n log n log m)在10^5数据量下完全跑得动。#include bits/stdc.h using namespace std; int n, m; vectorlong long t; bool check(long long T) { priority_queuelong long, vectorlong long, greaterlong long pq; for (int i 0; i m; i) pq.push(0); for (int i n - 1; i 0; i--) { long long cur pq.top(); pq.pop(); if (cur t[i] T) return false; pq.push(cur t[i]); } return true; } int main() { cin n m; t.resize(n); for (int i 0; i n; i) cin t[i]; sort(t.begin(), t.end()); // 升序排列从大到小取 long long left 0, right 2e18; // 答案下界是0上界给一个足够大的值 while (left right) { long long mid (left right) / 2; if (check(mid)) { right mid; } else { left mid 1; } } cout left endl; return 0; }这里有个编码细节值得单独说right的初始值不要设成某个拍脑袋的数我一般用2e18这种远大于理论极限的值保证二分范围一定能覆盖答案。另外sort之后如果直接用升序任务会从耗时最短的开始分配这通常是错的。正确的做法是从耗时最长的任务开始分配因为这样才能让所有机器尽量均衡地分摊负载。我在代码里是从循环变量i从n-1倒着取的这样可以避免再写一次反向排序。这个题对时间分配的要求也很高。如果check函数写错了方向、二分边界处理漏了一个等号都是直接WA而且这类错误在本地测试时不一定能暴露出来。所以在正式编码前我习惯先用小数据手动模拟一下二分收敛过程把left和right的收敛顺序写清楚再动手。3. 实操过程从读题到AC的完整决策链3.1 正确的时间分配先把送分题拿稳再啃硬骨头两小时做四道题时间非常紧张。我的策略一直是“先易后难、先AC后优化”。第三场的题量其实不算大但编码和调试时间会失控尤其是第四题这种需要状态压缩的动态规划题很容易一写就是一个小时。我在考场上给四道题的建议时间分配是第一题15分钟第二题25分钟第三题40分钟第四题40分钟剩下的时间做检查和补充边界数据测试。这个分配方案的前提是你能在30秒内识别出每道题的核心算法模型。如果一道题读完三分钟后还没头绪我建议先跳过不要恋战因为后面的题未必比它难。第一题通常是个贪心题我花的时间通常更少因为在看题面的时候就能大致判断出是排序加遍历。比如某种通过调整顺序来优化总代价的题典型的思路就是把元素按关键字段排序再用一个值维护当前状态。这个题型的核心就是“排序后不留回头路”需要注意的就是排序规则如何设计——通常需要手写一个comparator而不是简单地按值升序或降序。我在考场上的经验是第一题虽然简单但一定不要轻视。因为笔试环境的判题系统是白盒评分一个数据点一个数据点地过你漏了某个边界条件就会挂掉一个子任务。比如排序题里数组为空、n1、所有元素相等等等这些边界情况是判题系统最爱隐藏的“陷阱”。我自己会刻意在写完代码后补跑几组极端小数据比如n1、全相同元素、最大最小值混合等。3.2 第二三四题的编码节奏每个环节容易卡壳的地方第二题如果想到差分数组编码很快真正的坑在“偏移量”。题目里数组下标往往从1开始但C数组从0开始如果你直接把区间[l, r]映射成数组的[l-1, r-1]差分代码很容易在边界上出错。我用了一个小技巧开n2大小的数组所有操作都用1-based下标最后输出时从下标1遍历到n把下标0的位置空着不用。这样可以完全避开偏移量换算的烦恼。第三题二分答案的边界处理是最大的坑。left和right的初始值怎么给、mid怎么取、check(mid)成立时是收缩哪一侧这三个问题如果没想清楚代码就会在某个数据点上陷入死循环或返回错误结果。我的经验是二分写完后用两个相邻的数据点手动推演一遍收敛过程比如答案恰好是某个数时left会不会正确地收敛到它。如果答案范围很大我还会在check函数里提前返回false减少无效计算。第四题动态规划我在这里分享一个状态定义的技巧。这类题往往需要你用若干种状态来表示当前处理到的位置并维护某一类代价的最值。不要一上来就试图用多维数组硬存所有状态先看状态之间是否存在冗余能不能用滚动数组压缩。我当时在做这题时先把二维转移方程写在草稿纸上然后用滚动数组把第一维优化掉最后把代码从二维数组改成两个一维数组空间复杂度从O(n×m)降到了O(m)。如果中间某个转移方程依赖上一层的多个状态滚动数组改造时要注意更新顺序防止覆盖掉还没被用到的旧值。3.3 考场环境适应本地能跑不代表提交能过校招笔试的编程环境一般支持主流的编程语言但每个平台对输入输出的细节要求不太一样。有的平台用标准输入输出有的平台封装了输入接口有的平台要求类名必须是Main。我见过不少人在本地IDE里用文件输入输出提交时忘了改直接编译错误。这是一个很低级但非常常见的失误。另一个常见问题是递归导致栈溢出。某些题用递归写法最直观但笔试环境往往不会给你调大线程栈的机会当数据量到10^5级别时递归深度过深就会爆栈。我的建议是能用迭代就尽量迭代实在要用递归就先算一下最大递归深度如果超过1万层就考虑改写为栈模拟。第三场题里虽然没有明显的递归题但如果你用递归实现某个二分搜索或图遍历就有可能触发这个问题。还有一个需要提前确认的事项是内存限制——美团笔试通常内存限制在256MB或512MB左右。如果你开了太多大数组Java的boolea数组、C的vector嵌套过多都有可能导致MLE。做题前先粗略估算一下所用数据结构的内存占用比如一个10^5级别的long long数组大约是0.8MB开十个左右没问题但如果开10^6级别且每个又是一个pair数组那就要小心了。4. 常见问题与排查技巧我在这套题上踩过的坑和总结出的速查表4.1 高频报错与解决办法我把自己和身边同学的共同踩坑记录整理成了一张表这里面的问题基本覆盖了笔试时所有常见的过不了类型错误类型典型表现常见原因解决办法WA答案错误本地测试正确提交后某个点失败边界条件未处理如n1、空数组用边界小数据自查写对拍脚本TLE超时数据量一大就超时算法复杂度不符合数据范围重新确认算法模型考虑二分/差分等优化MLE超内存运行时提示内存不足数组开得过大或使用递归栈压缩数组维度改用滚动数组或迭代RE运行错误数组越界或空指针下标偏移没算清楚统一使用1-based下标检查访问范围CE编译错误提交时编译失败平台类名或包名要求不符提前确认平台使用规范这张表里最值得展开说的是WA问题。我刷题时养成了一个习惯在写完代码后不只是跑题目给的样例而是自己构造几组“刁钻”数据。对于数组类题目我至少会测试n1、n2、所有元素相同、所有元素逆序排列、包含最大值和最小值混合等几个特殊情况。说实话很多笔试的隐藏数据点考的就是这些边界情况并不是算法思路本身有问题。4.2 本地自测与对拍一个实用的小方法这里分享一个非常实用的自查方法——对拍。简单来说就是写一个暴力解法保证正确性但可能超时和一个优化解法你提交的版本然后随机生成小规模数据对比两个解法的输出是否一致。如果不一致说明优化解法在某个细节上写错了再逐年缩小数据范围定位错误。对拍脚本在小数据下可以快速发现问题这是补全边界测试的好方式。笔试时没有条件写脚本对拍所以我建议平时刷题时多练习“手动构造数据”的能力。选择题一个方向如果我是出题人我会在哪个数据点卡人正常人都会想到的边界、极端值、重复值、超大值等等这些都是优先测试的点。4.3 在笔试中遇到“没见过”的题怎么办第三场第四题如果第一次接触确实容易懵。我的经验是遇到没见过的算法题先不要慌回到最原始的问题定义上试着把题目转换成已知模型。比如题目要求“最值”你可以想想是否能用二分答案或动态规划题目涉及“区间操作”你可以想想是否能用差分或前缀和。大多数笔试算法题本质上是几个常见的算法模型的组合不存在“完全凭空造出来”的算法。如果转换不了就用暴力法先拿部分分数。美团笔试通常采用分组数据如20%的小数据、40%的中等数据、40%的大数据暴力写法至少能通过小规模数据点的测试。我看过一些人因为想一步到位写出最优解结果思路卡住最后连暴力分都没拿反而比那些“先暴力再优化”的人总分低。笔试的目标是拿分不是炫技。5. 复盘与扩展如何把这场题变成自己的算法能力5.1 从一道题扩展出一类题以差分数组为例第三场第二题用差分数组解决区间加问题但如果只会这一道题下次换个马甲你照样不会。我自己的方法是每做完一道题就总结一下这类题型的“识别特征”和“通用解法”。比如差分数组的识别特征就是多次区间操作、单点查询或最终整体查询、数据量大不能暴力模拟。一般解法很固定所有区间操作用差分数组记录下来最后求一次前缀和还原。同样地二分答案的识别特征是“最大最小化”或“最小最大化”check函数的构造方式通常和贪心策略绑定。遇到这类题我第一件事就是画一个数轴把可能的答案范围标出来然后思考“如果答案提高1单位可行域怎么变化”。这样整理下来你刷的不是一道题而是一类题。下次遇到“区间异或更新”“二维差分”这些变体也能迁移过去。5.2 后续学习建议把笔试当成算法训练的一块跳板说实话校招笔试的算法题不会直接出现在日常业务开发中。你写一个用户订单系统不会真的需要二分答案去优化某个查询。但笔试考的是你的思维习惯面对一个复杂问题能不能拆解成已有模型能不能在可控时间内给出可运行的解。这种能力是长期受用的。我建议准备校招的朋友不要把目标定在“背题”上而是把常见算法模型刷透尤其是贪心、二分、动态规划、前缀和差分、基础图论BFS/DFS这几类。美团第三场笔试覆盖的考点恰恰是互联网大厂笔试里出现频率最高的几个。把这几个核心模型练到“看到题就能归类”的程度比盲目刷300道冷门题要高效得多。5.3 最后再说一个实操层面的小技巧我不建议在笔试前临时刷大量新题。考试前两到三天应该做的是复习自己总结过的错题和经典题型同时把每个算法的模板代码在编辑器里重新敲一遍确保肌肉记忆。真正到了考场决定你成绩的不是爆发力而是平时积累的稳定度。第三场这套题如果说非要挑一句最有价值的复盘心得我想是识别算法模型的速度比你会多少种高级数据结构重要得多。差分数组替代线段树贪心替代复杂度证明这些都是“更聪明地解决问题”的体现。把基础模型吃透你在任何一家大厂的校招笔试里都不会吃亏。