这一场笔试我是事后复盘完才敢动笔写的因为当场出来的时候整个人是有点懵的。美团2023校招技术第6场编程题整体难度不算变态但它的区分度其实不在“题目有多难”而在“你能不能稳”。四个题覆盖了模拟、双指针、拓扑排序、动态规划正好是校招笔试里最常出现、也最容易拉开差距的几个方向。这篇文章我把四道题按记忆还原出来每道题都给出完整的题目模型、思路推导、代码实现和复杂度分析最后再聊聊我在考场上踩的坑和一些关于校招笔试的实在建议。如果你正在准备互联网大厂的校招笔试这篇应该能帮你少走不少弯路。1. 题目概览与整体感受1.1 这一场笔试的结构美团的技术笔试一般是四个编程题时间大概两个小时。第6场这套题从布局上非常有代表性第一题是纯模拟第二题是双指针加滑动窗口第三题是拓扑排序套了一个关键路径的壳第四题是线性动态规划加优化。四个题目没有一个考冷门算法全是LeetCode中等题里反复出现的套路但实际做起来会发现每个题都有个隐蔽的坑考察的是你“能不能在压力下写对”。整场笔试的时间分配很关键。我当时的策略是先花两分钟把四个题全部看完对难度有个基本判断然后从第一题开始按顺序做不跳题。这样做的好处是心理上有节奏感不会因为某道题卡住就导致后面的题完全没时间看。实际上前面两题如果平时刷题够多是可以比较快拿下的真正决定排名的往往是第三题和第四题。1.2 看完四道题的第一反应我记得当时扫完四道题的第一反应是没有特别恶心的计算几何也没有那种需要高级数据结构的题但第三题和第四题都不是送分题需要花时间想清楚再动手。第一题看起来最友好但模拟题最容易翻车的地方不是逻辑而是边界条件。第二题是典型的滑动窗口往年也常考关键是维护窗口内的最大最小值时要选对数据结构。第三题猛一看以为是普通拓扑排序实际上它要求的是“所有任务并行执行时的最短完成时间”这就在拓扑排序的基础上多了关键路径的思想。第四题是经典的选择问题但n的范围给得比较大暴力DP过不了需要优化。我当时心里大概排了个优先级第一题必须拿满分第二题尽量满分第三题保底拿部分分第四题暴力先保底再优化。这个策略基本贯彻到了最后。2. 第一题签到题也要小心边界2.1 题目还原与考察点题目大概是这样的给定一个长度为n的正整数数组a每一轮操作从数组的第一个元素开始依次扫描相邻的两个元素a[i]和a[i1]如果它们都是偶数就把两个数合并成一个新数a[i] a[i1]或者说用它们的和替换掉这两个数合并之后继续从当前下标的下一个位置往后扫描而不是重新从头部开始。这样执行恰好m轮操作后输出最终的数组。这个题的考察点非常纯粹你能不能把一个不断变化的数组操作模拟清楚。它不是算法题是“工程题”。很多人看到这种题的第一反应是直接开个vector然后暴力删元素这在n比较小的时候没问题但如果n给到10的5次方m也给得很大频繁的插入删除就会超时。我在考场上选择了双端队列加辅助数组的做法。一个临时容器存放当前这一轮处理后的结果另一个临时容器存放“合并出来的新数”然后下一轮再处理。这样每一轮只需要线性地扫一遍数据整体的时间复杂度是O(n * m)如果m也给得很大需要再想办法但这个题给的范围用这个做法是稳的。2.2 代码实现与边界细节这道题的核心代码大概长这样我用C写出来#include bits/stdc.h using namespace std; int main() { int n, m; cin n m; vectorlong long a(n); for (int i 0; i n; i) cin a[i]; while (m--) { vectorlong long b; int i 0; while (i a.size()) { if (i 1 a.size() a[i] % 2 0 a[i 1] % 2 0) { b.push_back(a[i] a[i 1]); i 2; } else { b.push_back(a[i]); i; } } a b; // 如果数组长度已经变成1后面再怎么合并结果都不变了 if (a.size() 1) break; } for (int i 0; i a.size(); i) { if (i) cout ; cout a[i]; } cout endl; return 0; }这里有几个关键的边界处理我现场差点踩进去合并之后不能立刻接着判断合并出来的新数与下一个原元素因为题意要求“从当前下标的下一个位置继续扫描”也就是说合并完两个元素后i要跳过两个位置而不是只跳一个。我最初的写法是在合并后让i结果合并产生的数值被错误地参与了新一轮比较样例都过不了。有可能某一轮没有任何合并发生这时数组不变可以直接提前结束避免无意义的循环。注意整型溢出两个偶数相加假如a[i]本身给到了10的9次方量级int就会爆要用long long存储。2.3 为什么第一题容易翻车这种题在笔试里被叫作“签到题”但签到题不等于送分题。它的AC率往往不是最高的原因很简单人人都觉得简单人人写出来的细节都不一样边界一多就有人挂。我印象特别深的是当时同考场有人用了一个非常取巧的方式先把所有偶数找出来两两配对然后再重组数组。这个思路在“可以任意重新排序”的前提下是对的但这个题的合并必须严格按照原数组顺序进行所以他的做法在部分测试点上是错的。我个人的经验是模拟题一定要先自己在纸上把“一轮操作”的过程走一遍把数组下标变化的规律写清楚再动键盘。千万不要一边写代码一边想逻辑那样最容易在细节上漏掉东西。尤其是这种“合并后继续向后扫描”的规则一定要想清楚i的步进是1还是2。3. 第二题滑动窗口的经典变体3.1 题目还原与考点拆解第二题大概是这样给定一个长度为n的数组a以及一个整数x。要求找到最长的一个连续子数组使得这个子数组中元素的最大值与最小值之差不超过x。输出这个最长子数组的长度。这个题一看就是双指针滑动窗口。核心的难点在于当右指针移动的时候窗口内的最大值和最小值是动态变化的左指针收缩的时候也要同步更新最大值和最小值。如果每次都用暴力去重新算复杂度就是O(n^2)必挂。我当时想到的方案是维护两个单调队列一个维护窗口内的最大值一个维护窗口内的最小值。滑动窗口的经典做法最大值队列保持单调递减队头就是当前窗口的最大值最小值队列保持单调递增队头就是当前窗口的最小值。每次移动右指针把新元素分别插入两个队列每次收缩左指针在弹出元素时判断队列头部是否要跟着弹出。为了方便展示用multiset实现是最直观的虽然复杂度多了个log n但在笔试环境下更不容易写错#include bits/stdc.h using namespace std; int main() { int n, x; cin n x; vectorint a(n); for (int i 0; i n; i) cin a[i]; multisetint ms; int left 0, ans 0; for (int right 0; right n; right) { ms.insert(a[right]); while (*ms.rbegin() - *ms.begin() x) { // 删除元素时要用find直接传值会把所有相同元素都删掉 ms.erase(ms.find(a[left])); left; } ans max(ans, right - left 1); } cout ans endl; return 0; }3.2 双指针实现与复杂度用multiset的时间复杂度是O(n log n)空间复杂度是O(n)。这个复杂度在n为10的5次方级别时完全可以通过实测运行时间在几百毫秒以内。如果要追求极致的性能可以用单调队列降到O(n)。我当时在考场上用的是multiset原因很简单笔试优先保证正确性和速度能用现成的STL容器就尽量用不给自己增加额外的心智负担。两个单调队列的实现不仅代码量大而且容易在“窗口收缩时队列头部元素到底该不该弹”这个问题上想不明白。不过这里有一个很细节的问题值得写出来也是我身边很多朋友在复盘时提到的一个坑multiset删除元素时如果直接写ms.erase(a[left])它会把所有值等于a[left]的元素全部删除而我们的窗口内可能有多个相同的值。正确写法是用ms.erase(ms.find(a[left]))只删除迭代器指向的那一个元素。这个坑特别隐蔽因为它在只有少数测试点会触发数据一大、重复元素一多就会错。3.3 我在考场上卡住的地方这道题我其实没有卡太久真正让我停顿了一下的是那个x的范围。题面里明确说了数组元素可能为负数当时我头脑里瞬间闪过一个念头rbegin - begin是不是还要取绝对值其实不需要因为rbegin()是容器内最大的元素begin()是最小的元素前者减后者天然就是最大值与最小值之差不存在负数问题。这是一个很蠢的瞬间迟疑反而浪费了我大概两分钟。另外一个我复盘后才想到的点是这道题有一个隐藏的可优化版本如果题目要求输出的是满足条件的最长区间本身而不只是长度那就要在更新ans的时候把当前位置一起记录下来。这不算难但如果你只写了长度最后发现题目要求输出区间就得改一遍代码浪费时间。所以笔试时审题的那两分钟真的不能省一定要看清楚题目到底让你输出什么。关于滑动窗口这类题目我的建议是把“右指针扩张、左指针收缩、更新答案”这三步背下来形成肌肉记忆。笔试现场的思考时间要留给后面的算法题而不是浪费在最基本的套路题上。4. 第三题拓扑排序的隐蔽考法4.1 题目还原与转化思路第三题是这套卷子里第一个真正有区分度的题。题目设定大概是这样有n个任务编号从0到n-1每个任务有一个执行耗时cost[i]。有些任务之间存在依赖关系给定一个依赖列表每个依赖项是一个二元组(u, v)表示任务u必须在任务v开始之前完成或者说v依赖u。现在有足够多的机器所有没有依赖关系的任务可以同时开始执行。要求计算所有任务都完成的最早时间。这个题第一眼看上去就是拓扑排序但直接套拓扑排序模板会掉进陷阱。因为普通的拓扑排序只关心任务的执行顺序而这里问的是“最短完成时间”也就是在有足够并行资源的情况下整个项目从开始到结束需要多长时间。这就是经典的“关键路径”问题它在工程管理里叫CPMCritical Path Method在校招笔试里就是一个拓扑排序加上动态规划。核心思路是这样的一个任务的最早开始时间取决于它的所有前置任务中“完成时间最晚的那个”。因为任务v必须等所有依赖它的前置任务全部完成后才能开始。因此我们用拓扑序去推当处理到某个节点u时如果能松弛它的后继节点v就更新v的最早开始时间。最终答案就是所有任务“最早开始时间 自身耗时”中的最大值。4.2 拓扑排序与关键路径的完整实现我现场的代码如下#include bits/stdc.h using namespace std; int main() { int n, m; cin n m; vectorlong long cost(n); for (int i 0; i n; i) cin cost[i]; vectorvectorint g(n); vectorint indeg(n, 0); for (int i 0; i m; i) { int u, v; cin u v; // u 必须在 v 开始前完成 g[u].push_back(v); indeg[v]; } vectorlong long start(n, 0); // 每个任务的最早开始时间 queueint q; for (int i 0; i n; i) { if (indeg[i] 0) { q.push(i); } } int cnt 0; while (!q.empty()) { int u q.front(); q.pop(); cnt; for (int v : g[u]) { // v 的最早开始时间要覆盖所有前置任务完成的时间 start[v] max(start[v], start[u] cost[u]); indeg[v]--; if (indeg[v] 0) { q.push(v); } } } // 如果cnt n说明有环正常题目不会给这种数据 long long ans 0; for (int i 0; i n; i) { ans max(ans, start[i] cost[i]); } cout ans endl; return 0; }这个代码里有几个地方值得多说一句。首先是为什么用max而不是直接赋值因为一个任务可能有多个前置任务每个前置任务完成的时间不同必须要取最大值才能保证所有前置任务都完成了。其次是拓扑排序过程中入度减到0才入队这个标准操作的目的是保证我们处理某个节点时它的所有前置节点都已经处理完毕这样start数组的推导才是可靠的。4.3 现场卡住的原因我在这道题上卡了大概十五分钟不是因为拓扑排序不会写而是因为当时觉得“既然机器无限那所有入度为0的任务可以同时开始是不是直接把所有节点的cost加起来除以并行度之类的”这个想法很快被自己否定了因为并行度是无限的不存在“除以几”的问题最终时间只取决于最长的那条依赖链。还有一个让我犹豫的点是任务u必须在任务v开始前完成这句话到底是谁指向谁如果按字面意思u是v的前置任务那么建图应该是u指向v入度加在v身上。但有些人可能会理解反了把图建反导致拓扑排序跑出来的结果完全错掉。这种方向性的问题在考场上特别容易发生我的建议是拿到题先画一个小数据例子手动推一遍再开始写代码不要省这一步。这里也顺手提一下这个题如果所有任务之间都没有依赖关系那么答案就是所有任务耗时的最大值因为所有任务可以同时开始执行。如果有一条依赖链特别长那么最终答案大概率由这条链决定。把这个直觉建立起来对理解和写出正确的DP转移会有很大帮助。5. 第四题动态规划的优化5.1 题目还原第四题是压轴题出的是一道线性DP的变体。题目大意是给定一个长度为n的数组a要求从中选出若干个位置不能选择相邻的位置并且任意两个被选位置之间的距离不能小于k求选出的数之和的最大值。这个题就是“打家劫舍”的加强版。普通的打家劫舍要求不能选相邻的两个位置这里把限制变成了“距离至少k”也就是i和j之间至少有k-1个位置没被选。n的范围是2 * 10的5次方a[i]可以是负数。如果直接用O(nk)的DP在k很大的时候会直接超时。需要定义dp[i]表示“只考虑前i个位置且第i个位置必选时能获得的最大和”。那么转移方程就是dp[i] a[i] sum_{j i-k} max(dp[j], 0)这里为什么是max(dp[j], 0)因为如果前面某个位置的最优值是负数那不如不选它直接让前面为空。这样处理负数的逻辑就比较优雅。5.2 状态转移与优化思路第一版代码如果直接按这个转移方程做内层循环要枚举所有j复杂度是O(n^2)肯定不行。我们需要用一个前缀最大值来快速获取[0, i-k]这个区间内dp[j]的最大值这样就能把转移优化到O(n)。具体做法是用一个preMax数组preMax[i] max(preMax[i-1], dp[i])。那么转移的时候只需要取preMax[i-k]就行。代码如下#include bits/stdc.h using namespace std; int main() { int n, k; cin n k; vectorlong long a(n 1); for (int i 1; i n; i) cin a[i]; vectorlong long dp(n 1, 0); vectorlong long preMax(n 1, 0); for (int i 1; i n; i) { if (i - k 0) { dp[i] a[i] max(0LL, preMax[i - k]); } else { dp[i] a[i]; // 前面放不下任何“距离至少k”的位置了 } preMax[i] max(preMax[i - 1], dp[i]); } cout preMax[n] endl; return 0; }这里有一个需要特别注意的边界问题当i k的时候第i个位置前面能选的区间是空的所以不能依赖前面的位置dp[i]只能等于a[i]。但这里有个反直觉的点如果a[i]是负数它会不会拉了整个答案的后腿不会因为我们在最后取preMax[n]的时候已经保证了答案不会因为某个负数选择而变小因为preMax取的是所有dp的最大值它相当于考虑了“这个位置不选”的情况。5.3 另一个优化方向线段树如果你在考场上没想起来用前缀最大值线段树也是一个可靠的选择。用线段树维护dp值区间最大值每次查询[0, i-k]区间内的最大值复杂度同样是O(n log n)对于n 2 * 10^5是能过的。但我个人建议如果思维转得过来优先用前缀最大值。因为O(n)的复杂度更稳而且代码量少很多不容易bug。线段树的优势在于如果题目再改一下变成“区间内有些位置不能用”那线段树就能灵活处理。不过校招笔试一般不会把题目复杂到那个程度所以用最简单的方案就够了。这道题还有一个细节容易被忽略a[i]可能是负数负数可不可以选答案是“可以但不推荐”因为dp的定义是“第i个位置必选”所以负数也会被选进来只是它会导致这个状态值变小最终答案在取preMax时自然会跳过它。如果你把状态定义成“前i个位置的最大和”第i个位置可选可不选那DP转移会变成另一种写法要注意区分。6. 笔试复盘策略、时间分配与准备建议6.1 这场笔试的时间策略复盘笔试一共两个小时我实际的时间分配是这样的前10分钟看四道题并建立初步思路第一题花15分钟写完并通过样例第二题花20分钟写完第三题卡了接近30分钟其中有好几分钟在犹豫依赖方向第四题写DP加优化花了25分钟剩下大概20分钟用来回头检查边界和测试极端情况。最终我的个人体感是第一题和第二题属于“必须稳拿”的部分第三题如果不卡那15分钟能省出更多时间给第四题做更稳妥的验证。校招笔试的评分通常不只看通过几个测试点还会参考你提交代码的时间和完善程度所以尽量给后面的题留出缓冲时间。6.2 踩坑清单速查我把这套题里值得注意的坑整理成了一个表格方便你对照着检查自己的代码题目核心考点最容易踩的坑建议处置方式第一题 模拟合并数组操作与边界合并后下标步进写错int溢出先纸面推演一轮用long long第二题 滑动窗口双指针 动态最值multiset删除元素误删重复值用erase(find())而不是直接传值第三题 拓扑关键路径最长依赖链依赖方向建反start转移忘记取max先画样例图理清谁指向谁第四题 线性DP优化前缀最大值优化负数处理不当边界i-k 0时dp初始化错误明确dp定义善用preMax除了表里的内容我还想额外说一个关于输出格式的坑四道题都要求输出严格格式不能有多余空格不能有多余换行。很多人算法写对了但因为最后的输出循环里多了一个空格导致格式错误白丢分。我习惯把输出逻辑写成一个从0开始的循环判断if (i) cout 这样就不会有多余空格。6.3 给准备校招的同学的实用建议如果你正在准备校招我的建议是不要盲目刷题海而是按高频考点分模块刷。根据这套题的特征美团以及其他大厂的技术笔试往往集中在几个方向上数组和字符串操作、双指针与滑动窗口、栈与队列、二叉树、图论基础尤其是拓扑排序、线性DP、背包DP、贪心和二分。这些方向每个练熟20到30道题基本就能覆盖笔试的大多数题目。考场上还有一个容易被低估的策略不要长时间卡在一道题上。如果你15分钟内还没有任何思路果断跳下一题先把所有会做的题拿到分再回头啃硬骨头。笔试是看总分排名不是看单题满分所以整体收益最大化才是正确的目标。另外强烈的建议是多做模拟题。市面上的各类题库里都能找到往年校招真题虽然每场题不一样但同一家公司的出题风格和难度分布是有连续性的。看到“美团2023校招技术第6场编程题”这类标题不要只看题解要自己动手限时写一遍模拟真实的考场状态。大量的模拟练习之后你对时间的把握和代码的稳定性都会有明显提升。根据我个人的经验笔试的临场心态比很多同学想象中重要。遇到没见过的题先别慌它大概率是某个已知套路换了个壳。把题目拆成“数据规模 操作类型 询问目标”三个维度去分析选路和优化思路往往很快就清晰了。这一场六题的经验就是这样希望对你接下来的校招笔试准备有所帮助。