这套题我拖了整整两周才整理完不是因为题目难得离谱而是网上流传的回忆版代码质量参差不齐有的把输入输出格式都写错了有的样例都跑不通。我把能找到的几份版本对了一遍重新按自己的规范写了完整复盘也把每道题背后美团想考察的能力拆开讲清楚。美团2023校招技术类笔试线上平台做题两个小时左右题量一般在3到4道之间。第7场对应的是秋招批次里比较靠后的场次但考的东西其实并不冷门一道贪心签到题、一道二分答案、一道BFS加状态压缩DP正好覆盖了校招笔试最高频的三类考点。对正在准备大厂笔试的同学来说这套题的参考价值不在于题目多新而在于难度梯度太典型了——第一题保基础第二题考二分基本功第三题才是真正拉开差距的地方。下面按题目逐一复盘。代码统一用C17写平台输入输出风格按牛客和赛码的常见规范处理直接可以本地跑。1. 从一套回忆版赛题说起第7场到底考了什么先说一个很多人忽略的事实这类校招编程题在笔试结束之后题目并不会公开你能在网上搜到的基本都是参加考试的同学靠着记忆拼出来的“回忆版”。既然是回忆版细节就可能和原题有出入比如数据范围记错、输入格式记反、或者某个边界条件被省略。我整理这份复盘时不敢说自己还原了100%的原题但题目的核心考点和解题思路是确定的这也是这套题最有价值的部分。1.1 这场笔试的整体情况按照美团2023校招技术岗的统一节奏技术笔试一般安排1到2个小时在赛码或牛客这类OJ上完成。题目的分值分布很典型前一两道题属于“送分题”保证基础扎实的同学能拿到足够多的分数中间一到两道题属于“拉分题”考经典算法的迁移能力最后一道压轴题往往是综合题需要把图论、搜索、动态规划这些东西组合起来用。这场第7场的题目可以归纳成下面这张表后面的章节会对每题做详细拆解题目核心算法难度定位建议用时骑手取餐调度贪心 模拟签到题10分钟站点检查二分答案 贪心判定中等25分钟同城速递BFS 状态压缩DP压轴40分钟这个时间分配不是绝对的但大致符合“先易后难、控制节奏”的答题思路。我见过很多同学在第三题上死磕一个小时结果前两题因为粗心丢了分非常可惜。1.2 关于回忆版题目的整理约定因为网上流传的版本太乱我统一做了几件事第一所有题目的输入输出格式按最常见的OJ风格重写保证可以直接用标准输入输出跑通第二代码全部用C17并注释了关键步骤方便C和Java背景的同学都能看懂第三每道题都补了边界情况的处理逻辑因为校招笔试的测试用例最喜欢在边界上卡人。另外说明一下如果读者在某道题的细节上看到的版本和我这里不完全一致不用太纠结重点去理解“这道题考什么、为什么这样解、换一个场景还能不能套用”。面试官真正想看到的是你对经典模型的掌握程度而不是背题。2. 第1题“骑手取餐调度”把贪心签到题做到不丢分这套题的第一题非常友好属于那种刷过几十道简单题就能秒掉的类型。但越是这样的题越容易在一些不起眼的边界上翻车。后面我会重点讲那个坑。2.1 题目原貌与输入输出题目大意是午餐高峰期骑手小明负责一条线路上的N个取餐点每个取餐点需要花费一定时间完成取餐并且必须按照编号从小到大的顺序依次取。由于餐箱容量和路线限制小明跑一趟最多只能连续处理耗时总和不超过W的若干个取餐点超过就需要回到配送点重新出发即开启下一趟。问最少需要跑几趟才能取完全部外卖如果某个取餐点的耗时单独就超过W说明一趟根本装不下这个点整个任务无法完成输出-1。输入输出格式如下输入 5 6 2 3 1 5 2 输出 3样例的含义是5个取餐点单趟容量W6。可以分成 [2,3,1]、[5]、[2] 三趟也可以分成 [2,3]、[1,5]、[2] 三趟但怎么分都不可能少于3趟所以答案是3。2.2 核心思路为什么贪心是最优的这道题的本质是给定一个全是正整数的数组要求把它切成若干连续段使得每段的和不超过W求最少段数。先说结论从左往右扫描能装就装装不下就开新段这就是最优解不需要动态规划也不需要用别的复杂优化。很多同学会疑惑贪心策略真的不会漏掉最优解吗这里我给一个直观的说明。假设在第i个取餐点当前这趟已经装了cur的总耗时如果cur a[i]没有超过W那么把这个点放进当前这趟一定不会让结果变差。因为如果把它放到下一趟只会让下一趟的负担增加而当前这趟的剩余空间被浪费掉总趟数不可能因此减少。这就是“贪心选最近可行解”的正确性来源。这个逻辑成立的前提是数组里全是正数。如果存在负数贪心就不一定对了因为塞进一个负数可以让当前段的和变小从而容纳更多后面的点。但题目给出的取餐耗时都是正数所以贪心没有问题。实现上需要注意几个细节。cnt的初始值要设置为1因为在不考虑空数组的情况下至少会有1趟。然后维护一个cur表示当前趟已经累计的耗时每读入一个x先判断cur x是否大于W如果大于说明当前这趟装不下x了就开启新的一趟cnt加1同时把cur重置为x如果小于等于W就直接把x累加到cur里。还有一个很容易忽略的情况如果x本身大于W也就是某个取餐点单点耗时已经超过了一趟的容量限制那么整个任务无解最终输出-1。做判断时不能遇到x W就直接break因为题目的输入还没有读完直接跳出会影响后续数据的读取导致程序行为异常。正确做法是设置一个标记继续读完输入最后统一判断。累加变量cur最好使用long long。虽然W不一定很大但题目没有明确说明N的范围时数组总和可能会超出int的表示范围用int去累加容易出现溢出这类低级错误在校招笔试中很致命。2.4 参考实现与复杂度#include bits/stdc.h using namespace std; int main() { int n; long long w; cin n w; long long cnt 1, cur 0; bool ok true; for (int i 0; i n; i) { long long x; cin x; if (x w) { ok false; continue; } if (cur x w) { cnt; cur x; } else { cur x; } } if (!ok) cout -1 endl; else cout cnt endl; return 0; }时间复杂度是O(N)只需要一次数组遍历空间复杂度O(1)。这道题的目标就是稳拿满分代码不应有任何多余的复杂度。如果你在笔试现场卡了很久多半是没注意到单点超时的无解判断这个问题在真实用例里几乎一定会出现。3. 第2题“站点检查”二分答案题如何快速找到单调性第二题开始有区分度了但本质上仍然是经典题。美团很爱考这类“最小化最大值”的题目因为它对二分思想和贪心check都有要求代码量不大但陷阱不少。3.1 从“最小化最大值”到“给定上限判断可行性”题目大意美团有N个外卖站点排成一条街每个站点的检查耗时为a[i]。现在有K名检查员每个检查员可以负责一段连续编号的站点他负责的所有站点总检查耗时不能超过某个上限L。请设计一种分配方案把全部站点检查完并让这个上限L尽可能小。求最小的L。这题的突破口是“最小化最大值”这个信号。直接求L很难因为站点顺序固定、人数固定似乎要考虑怎么切分才最均匀。但如果反过来给定一个上限L问“能否用不超过K个检查员完成任务”这就是一个非常简单的贪心问题。于是整个问题就变成了二分Lcheck(L)返回“用不超过K段能否覆盖全部站点并且每段的和不超过L”。3.2 单调性与二分边界为什么可以二分因为L越大每段能容纳的站点就越多需要的段数只会更少或不变。也就是说check(L)是一个单调的函数当L增大到一定程度后一定可以从false变成true。既然有单调性就可以用二分在可能的上限取值区间里查找最小的可行L。二分的下界应该是所有a[i]的最大值。原因是一个段至少要包含一个站点如果L小于某个站点的耗时那么连单独检查这个站点都做不到肯定无解。二分的上界应该是所有a[i]的总和因为如果只有一个检查员他可以检查全部站点此时L等于总和一定可行且不可能需要比总和更大的L。有的同学习惯把左边界设为1这样也能跑但会多做一些无意义的二分循环。更关键的是如果某个a[i]特别大而你从1开始二分check函数里就得反复处理a[i] mid的情况虽然代码也不算错但不如直接把下界设为max(a[i])来得干净。3.3 check函数贪心地装check(L)的实现和第一题的贪心非常像。因为一个检查员可以负责任意连续段那么为了让检查员数量尽量少应该让每个检查员尽可能多地覆盖站点也就是从左到右累加一旦超过L就换下一个检查员。cnt 1 cur 0 for x in a: if cur x L: cnt 1 cur x else: cur x return cnt K注意两点。第一如果某个x本身大于Lcheck应该直接返回false因为这一个站点就已经无法被检查。虽然二分下界已经保证了mid不会小于max(a[i])但check函数作为一个独立函数还是应该具备这种防御性判断方便以后复用到别的问题上。第二cnt和cur都要用long long。N可以达到1e5级别总和会很大。3.4 参考实现与复杂度#include bits/stdc.h using namespace std; int main() { int n, k; cin n k; vectorlong long a(n); long long sum 0, mx 0; for (int i 0; i n; i) { cin a[i]; sum a[i]; mx max(mx, a[i]); } auto check [](long long limit) - bool { long long cnt 1, cur 0; for (long long x : a) { if (x limit) return false; if (cur x limit) { cnt; cur x; } else { cur x; } } return cnt k; }; long long l mx, r sum, ans sum; while (l r) { long long mid l (r - l) / 2; if (check(mid)) { ans mid; r mid - 1; } else { l mid 1; } } cout ans endl; return 0; }时间复杂度O(N log(sum))空间复杂度O(N)。对于N1e5的数据量几十次check完全可以接受。3.5 常见卡点我见过不少人在二分模板上翻车。有的用while(l r)配合mid (l r) / 2有的用while(l r)两种都能做对但最怕的是混着用。这里强烈建议固定一种写法比如上面的while(l r)配合ans记录当前可行解。这样即使最后l和r交错ans里也一定保存着最小的可行L。另一个容易错的点是二分时不要用mid (l r) / 2的写法如果l和r都是long long加法可能溢出。用l (r - l) / 2更安全。这道题里sum最多1e14左右int会溢出long long配合这个写法才稳妥。这道题美团常考本质上就是“最小值最大化”和“最大值最小化”这类二分答案模型的套壳。你只要看到“最X情况下尽量Y”而且数据范围达到1e5第一反应就应该是二分答案。4. 第3题“同城速递”BFS预处理状态压缩DP的压轴组合压轴题来了。这道题把美团的外卖配送场景和网格搜索结合得很自然难度也确实高了一个档次。它考的不是单一算法而是能不能把“BFS求最短路”和“状态压缩DP求最优路线的选择”这两件事有机地拼起来。4.1 先建立场景题目大意给一张n行m列的网格地图.表示可通行道路#表示障碍物S是骑手出发点地图上还有K个客户用数字1到K标出。骑手从S出发需要依次给这K个客户送完药品送完后必须回到S点提交订单。每移动一步耗时1分钟求送完所有客户并返回S的最短总时间。如果某个客户不可达输出-1。关键约束是K不超过6。这个数字不是随便给的它是解法的强暗示如果K很大就需要另外的算法K只有6意味着我们可以在K个客户之间做排列组合或者状态压缩DP。这里先强调一个容易搞错的地方题目中不会出现字符0起点统一用S客户统一用1到K表示避免和代码里的字符判断产生冲突。4.2 为什么不能直接在网格图上跑多目标搜索有人看到这题会想直接BFS状态就是当前位置加上已经送过的客户集合用三维数组dist[x][y][mask]来记忆化。思路本身没有错但地图可能很大比如n和m都是200K为6时状态数就是200×200×642560000个BFS展开起来内存和时间都压力很大。如果n和m扩大到500状态数会直接到1600万很容易超时。所以更好的做法是把问题拆成两层第一层用BFS求起点和K个客户两两之间的最短距离第二层在只有K1个节点的“小地图”上做状态压缩DP。这样一来BFS只需要跑K1次每次遍历整个网格图DP只处理2^K个状态计算量小到可以忽略。这个“先预处理点对点距离再做小规模DP”的思路是很多网格图上最短路线类题目的通用解法。4.3 第一层跑K1次BFS对每个关键点也就是起点S和每一个客户在原网格图上跑一次BFS得到它到地图上所有格子的最短距离。然后从这些结果中取出关键点两两之间的距离存到一个(K1)×(K1)的矩阵dis里。dis[0][i] 表示S到客户i的最短距离 dis[i][j] 表示客户i到客户j的最短距离 dis[i][0] 表示客户i回到S的最短距离如果某个dis[i][j]是无穷大说明两个关键点之间不可达整个问题无解直接输出-1。这里有一个工程细节每次BFS都会生成一个完整的n×m距离数组如果K比较大同时保存所有距离数组会占用较多内存。实际上我们只需要dis矩阵所以每次BFS完取出需要的数据后dist数组就可以释放了。在C里只要把BFS封装成一个函数返回dist二维数组主流程里取完dis就自然释放。BFS的写法没有特殊之处就是标准的四方向遍历遇到障碍物跳过。4.4 第二层状态压缩DP的掩码设计现在问题已经变成有K个节点以及一个起点已知任意两个节点之间的移动耗时求一条从起点出发、经过所有K个节点一次或多次、最后回到起点的最短路线。这里K≤6所以可以用一个长度为K的二进制数mask表示已经送达的客户集合。mask的第i位为1表示客户i已经送过。设dp[mask][i]表示当前已经送过的客户集合为mask且骑手最后停在客户i的位置时所用的最短时间。初始化比较直接从起点出发先去客户i那么dp[1i][i] dis[0][i]。转移也很直观当前停在客户i下一步去客户j如果j还没被送过那么dp[mask | (1j)][j] min(dp[mask | (1j)][j], dp[mask][i] dis[i][j])最后所有客户都送完后还要返回起点S。所以答案是ans min(dp[full][i] dis[i][0])其中full (1K) - 1i遍历0到K-1。这种状态设计是典型的“旅行商问题”变种。如果没有最后返回起点这一步它就是标准的遍历所有目标点求最短路径加上返回起点就变成了TSP的经典形式。K≤6的条件下暴力枚举6!种排列其实也可以过但状态压缩DP是更通用、更稳的写法代码也不复杂。4.5 小样例手推为了把dp过程讲清楚我给一个最小规模的样例3 3 1 S.1 ... ..#这里是3行3列地图K1。起点S在(0,0)客户1在(0,2)右下角(2,2)是障碍物。BFS结果S到客户1的最短距离是2路径是(0,0)-(0,1)-(0,2)客户1回S的路径也一样距离是2。初始化dp[1][0] dis[0][1] 2。最终答案dp[1][0] dis[1][0] 2 2 4。整个过程非常简单但已经完整走了一遍“BFS求距离DP求最优路线”的主线。当K变大的时候只是DP的状态和转移变多本质没有任何区别。4.6 参考实现与复杂度#include bits/stdc.h using namespace std; const int INF 0x3f3f3f3f; int n, m, K; vectorstring grid; int dx[4] {-1, 1, 0, 0}; int dy[4] {0, 0, -1, 1}; vectorvectorint bfs(int sx, int sy) { vectorvectorint dist(n, vectorint(m, INF)); queuepairint, int q; dist[sx][sy] 0; q.push({sx, sy}); while (!q.empty()) { auto p q.front(); q.pop(); int x p.first, y p.second; for (int d 0; d 4; d) { int nx x dx[d]; int ny y dy[d]; if (nx 0 || nx n || ny 0 || ny m) continue; if (grid[nx][ny] #) continue; if (dist[nx][ny] dist[x][y] 1) { dist[nx][ny] dist[x][y] 1; q.push({nx, ny}); } } } return dist; } int main() { cin n m K; grid.resize(n); vectorpairint, int pts(K 1); // 0号是起点S, 1~K是客户 for (int i 0; i n; i) { cin grid[i]; for (int j 0; j m; j) { if (grid[i][j] S) { pts[0] {i, j}; } else if (grid[i][j] 1 grid[i][j] 9) { int id grid[i][j] - 0; pts[id] {i, j}; } } } vectorvectorint dis(K 1, vectorint(K 1, INF)); for (int i 0; i K; i) { auto dist bfs(pts[i].first, pts[i].second); for (int j 0; j K; j) { dis[i][j] dist[pts[j].first][pts[j].second]; } } for (int i 1; i K; i) { if (dis[0][i] INF) { cout -1 endl; return 0; } } vectorvectorint dp(1 K, vectorint(K, INF)); for (int i 0; i K; i) { dp[1 i][i] dis[0][i 1]; } for (int mask 1; mask (1 K); mask) { for (int i 0; i K; i) { if (!(