企业官网建设流程全解析

三月底刷题群里有人甩了一份某出行平台3月22日春招笔试第二套的还原题，我第一时间就做了。说实话，这套题比我预想的温和，没有刻意炫技的偏题怪题，但三题各藏了一个“一眼看穿、细想全是坑”的点。考完复盘下来，我反而觉得这套题作为练手素材价值很高：它把图论最短路、区间调度DP、环形子数组三类高频题型一次性考全，而且每道题都能直接映射到出行行业的真实业务场景。这篇文章不搞虚的，直接给你逐题的考点拆解、完整代码、复杂度分析，以及我实际做题时踩过的坑。

也先说明一点：我拿到的是考生回忆版，题目描述和原始数据规模可能有细微出入，但核心考点和解题路径是不会变的。如果你也打算面出行类大厂，或者正在刷春招笔试，这套题的思路绝对值得完整过一遍。

1. 这套笔试题的考点全景与难度画像

1.1 三题的考点分布

先给个总览表格，方便你看完本文后按图索骥：

三题覆盖了笔试里最常考的三大板块：搜索与图论、动态规划、经典数据结构的变形应用。没有出线段树、平衡树这种竞赛味很重的考点，也没有纯数学题，整体风格偏向“工程场景 + 经典算法”，这是出行类大厂非常典型出题思路。

1.2 难度梯度与时间分配策略

整套题如果按正式笔试 90 分钟来算，我的建议分配是 15 分钟第一题、30 分钟第二题、15 分钟第三题，剩下 30 分钟全部留给调试和边界用例。

为什么第二题要留最长时间？因为它不是单纯套模板的 DP，还叠加了二分查找，而且排序顺序、下标映射、边界区间这三处任何一环出错都会导致答案错误，调试成本最高。第一题虽然要写 Dijkstra，但熟悉模板的人基本一遍过。第三题是经典原题的变形，知道“正难则反”的套路后反而最快。

做题顺序上，我个人的习惯是先做第三题热身，再做第一题，最后啃第二题。因为第三题代码量最小、思维量中等，能快速建立信心；第二题放最后，即使中途卡住，也不会影响前面两题的到手分数。笔试是按测试点给分的，能过一部分测试点就有分，这点和面试里“必须完全 AC”的心态完全不同，千万别在一题上死磕到交卷。

2. 第一题：网格地图中的最小体力消耗路径

2.1 题目描述与直观思路

题目大意是这样：给定一个 n * m 的网格地图，每个格子有状态，0 表示普通道路，1 表示施工路段，2 表示目的地。起点在左上角 (0, 0)，你每一步可以向上、下、左、右移动一格。经过普通道路消耗 1 点体力，经过施工路段消耗 2 点体力，到达目的地即结束。求从起点到目的地的最小体力消耗。

第一眼很多人会想：这不就是 BFS 吗？所有边权都是 1，BFS 一层层扩出去，第一次到达终点就是最优解。但这题的陷阱在于——经过施工路段代价是 2，不是 1，网格变成了一个边权为 1 或 2 的加权图。普通 BFS 的队列只保证步数最少，不保证体力消耗最小。

举个例子就能说明问题：一条路径全长 5 步、全程普通道路，体力消耗 5；另一条路径只有 3 步，但必须穿过两格施工路段，体力消耗是 2 + 1 + 2 = 5。如果按 BFS 的层数来算，后者步数少会先出队，但两者体力消耗相等；如果施工路段更多，短路径反而体力消耗更大。BFS 最短步数 ≠ 最小体力消耗，这个认知误差就是第一题的坑。

2.2 为什么这里必须用 Dijkstra

边权不全部相等的图，求单源最短路，标准做法就是 Dijkstra。核心思想是贪心地从当前体力消耗最小的格子向四周扩展，并用一个 dist 数组记录到达每个格子的最小消耗。因为边权都是正数（1 或 2），Dijkstra 的正确性有保障，不需要处理负权边，也不存在负环问题。

这题的数据规模，n 和 m 大概率在 10^3 量级以内，格子总数最多 10^6。用朴素 O(V^2) 的 Dijkstra 肯定不行，必须用优先队列优化的版本，复杂度是 O(V log V)，V 是格子总数。网格地图天然是稀疏图，每个格子只有四个邻居，优先队列版本完全吃得下。

实现上有两个细节提醒一下。第一，dist 数组一定要初始化为一个足够大的数，我用的是 1e9；第二，出队时要做一次“过期判断”，也就是如果当前取出的 d 已经大于 dist[x][y]，说明这个队首元素是旧数据，直接跳过，否则可能会用错误的状态去更新邻居。这两个细节看着不起眼，但丢了一个，大数据量下要么死循环、要么答案偏小，非常隐蔽。

2.3 完整代码与复杂度分析

#include <bits/stdc++.h> using namespace std; int main() { int n, m; cin >> n >> m; vector<vector<int>> g(n, vector<int>(m)); int sx = 0, sy = 0, tx = -1, ty = -1; for (int i = 0; i < n; ++i) { for (int j = 0; j < m; ++j) { cin >> g[i][j]; if (g[i][j] == 2) { tx = i; ty = j; } } } const int INF = 1e9; vector<vector<int>> dist(n, vector<int>(m, INF)); using State = tuple<int, int, int>; // (体力消耗, x, y) priority_queue<State, vector<State>, greater<State>> pq; dist[sx][sy] = 0; pq.emplace(0, sx, sy); int dx[4] = {-1, 1, 0, 0}; int dy[4] = {0, 0, -1, 1}; while (!pq.empty()) { auto [d, x, y] = pq.top(); pq.pop(); if (d != dist[x][y]) continue; // 过期状态，跳过 if (x == tx && y == ty) break; // 到达终点 for (int k = 0; k < 4; ++k) { int nx = x + dx[k]; int ny = y + dy[k]; if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue; int cost = (g[nx][ny] == 1 ? 2 : 1); if (d + cost < dist[nx][ny]) { dist[nx][ny] = d + cost; pq.emplace(d + cost, nx, ny); } } } cout << dist[tx][ty] << endl; return 0; }

复杂度上，每个格子最多入队四次（四个方向各触发一次更新），优先队列操作 O(log V)，总复杂度 O(V log V)，空间上需要 dist 数组和优先队列，O(V)。这个复杂度对于 10^6 量级的网格来说，实测跑满也就一两秒，稳过。

这里补充一个判断小技巧：如果你遇到边权只有 0 和 1 的图，可以用 0-1 BFS（双端队列）替代 Dijkstra，常数更小。但本题边权是 1 和 2，没有 0 边权，老老实实写 Dijkstra 就好，别为了炫技强行优化。

3. 第二题：订单调度的最大收益问题

3.1 题目描述与建模

第二题是整套题的分水岭，描述如下：某平台有 n 个预约订单，每个订单用一个三元组 (开始时间, 结束时间, 收益) 表示。司机同一时刻最多只能服务一个订单，订单之间可以无间隙衔接，也就是说一个订单的结束时间等于另一个订单的开始时间是被允许的。求司机在时间区间内能获得的最大总收益。

这个问题的业务背景非常直接，就是出行平台的司机接单调度：一个司机不可能同时接两个时间重叠的订单，但可以在完成一单后立刻接下一单。把每个订单抽象成“带收益的区间”，问题就变成了经典的带权区间调度（Weighted Interval Scheduling）。

看到区间、收益、互不冲突这三个关键词，第一反应必须是动态规划，而不是贪心。很多人在这一步会犯错，我展开讲讲为什么。

3.2 为什么贪心是错的

直观上，有人会想：按收益从大到小排序，能选就选，这不就是最大收益吗？反例很容易构造。有三个订单：

• 订单 A：时间 [1, 4]，收益 10
• 订单 B：时间 [2, 3]，收益 9
• 订单 C：时间 [3, 5]，收益 8

按收益排序先选 A（收益 10），但 A 和 B、C 都冲突，最后只能拿到 10；而如果选 B + C，总收益是 9 + 8 = 17，明显更优。所以贪心在这里完全不成立。

正确的做法是：按结束时间排序，然后做线性 DP。设 f[i] 表示在前 i 个订单（按结束时间排序后）中能获得的最大收益。对于第 i 个订单，有两种决策：不接，则 f[i] = f[i-1]；接，则必须找到在它开始时间之前就已经结束的最后一个订单 p，然后 f[i] = f[p] + 收益_i。两者取最大值。

关键在于“找最后一个不冲突的订单 p”。因为订单已经按结束时间排好序，所有结束时间 ≤ 当前订单开始时间的订单，都可以作为前驱。结束时间本身就是单调的，所以用二分查找找最后一个满足 end ≤ start 的订单即可，这也是为什么这题不是普通 O(n^2) DP，而是能优化到 O(n log n) 的原因。

3.3 二分查找与下标映射的细节

这题代码量不大，但二分边界很容易写错，尤其要注意排序是从下标 1 开始还是从 0 开始。我用的是从 1 开始存订单，这样 f[0] 可以安全地作为“没有前驱订单”时的基准值 0，避免数组越界的讨论。

二分查找时，我是在下标 [1, i-1] 范围内找最后一个满足 a[mid].end <= a[i].start 的订单。注意是“最后一个满足条件的”，不是“第一个”，两者二分方向不同。这里的关键是更新答案时记录 p，而不是直接返回 mid。如果区间内所有订单都不满足，p 保持初始值 0，对应 f[0] = 0，也就是当前订单之前没有任何可衔接的订单。

还有一个小细节：订单之间允许“结束时间等于开始时间”，所以二分判断条件是 end <= start，而不是 end < start。如果你写成严格小于，遇到边界衔接的用例会少算一种合法方案，答案就会偏小。

3.4 完整代码与正确性验证

#include <bits/stdc++.h> using namespace std; struct Order { int start, end, profit; }; int main() { int n; cin >> n; vector<Order> a(n + 1); for (int i = 1; i <= n; ++i) { cin >> a[i].start >> a[i].end >> a[i].profit; } // 按结束时间升序排序 sort(a.begin() + 1, a.end(), [](const Order& x, const Order& y) { return x.end < y.end; }); vector<int> f(n + 1, 0); for (int i = 1; i <= n; ++i) { int l = 1, r = i - 1, p = 0; while (l <= r) { int mid = (l + r) >> 1; if (a[mid].end <= a[i].start) { p = mid; l = mid + 1; } else { r = mid - 1; } } f[i] = max(f[i - 1], a[i].profit + f[p]); } cout << f[n] << endl; return 0; }

用刚才的反例验证：三个订单按结束时间排序后是 B（结束3）、A（结束4）、C（结束5）。计算 f[1] = max(f[0], 9 + f[0]) = 9；f[2] 时二分找 end ≤ 1 的订单，没有，p = 0，所以 f[2] = max(9, 10+0) = 10；f[3] 时二分找到 B（end=3 ≤ start=3），p=1，f[3] = max(10, 8 + f[1]) = max(10, 17) = 17。结果正确。

这里再提醒一句：如果题目数据量小（n ≤ 10^3），你甚至可以直接写 O(n^2) 的暴力 DP 找前驱，不需要二分。但笔试一般会给大数据量测试点，O(n^2) 会超时，所以二分优化是必写的。层序思考：先确认 DP 状态定义，再考虑如何快速求前驱，最后落到二分，这个思维链要比直接背模板靠谱得多。

4. 第三题：环形数组的最大子段和

4.1 题目描述与常规陷阱

第三题题干很短：给定一个环形整数数组，也就是说数组首尾相连，求环形子数组的最大和，子数组长度至少为 1。注意，如果是普通数组，这就是经典的 Kadane 算法；但环形数组意味着子数组可以跨越首尾边界，比如 [5, -3, 5] 这个普通数组的最大子段和是 7（取 [5, -3, 5]），但环形数组可以取 [5, 5]（首尾相连），最大和变成 10。

第一次做的同学很容易陷入一个误区：把数组复制一份变成长度为 2n 的数组，然后跑 Kadane。这个方法的问题是，长度为 n 的原数组复制后，一个跨边界的合法子数组会被正确计算，但同时也可能算出长度超过 n 的子数组，比如把整个 2n 数组全选进来，这对应到环形数组就是“绕了一圈多”，不是合法子数组。如果你再额外加一个长度限制，复杂度又会上升。所以我更推荐用分类讨论的做法。

4.2 “正难则反”的核心套路

环形子数组只有两种情况。第一种，不跨越边界，那就是普通数组的最大子段和，直接用 Kadane；第二种，跨越边界，此时可以反过来想：环形数组的总和是固定的，跨越边界的部分等于“去掉中间一段连续子数组”后剩下的部分。为了让剩下的部分最大，等价于让去掉的中间段最小，也就是求普通数组的最小子段和。

所以最终答案就是 max（普通最大子段和，数组总和 - 普通最小子段和）。这个套路的本质是“正难则反”：直接求跨越边界的最大段很麻烦，但求一个不跨越边界的最小段却非常简单，两者在数学上是对偶的。

这里有一个非常关键的边界情况：如果数组全部是负数，普通最大子段和是最大的那个负数（长度1），而“总和 - 最小子段和”会变成 0 或者一个不存在的空段，因为此时去掉最小子段（即整个数组或几乎整个数组）后剩下的部分是空的，空子数组是非法的。所以代码里必须先判断：如果最大子段和小于 0，直接返回最大子段和。

4.3 代码实现与边界用例

#include <bits/stdc++.h> using namespace std; int maxSubArray(const vector<int>& nums) { int cur = 0; int best = INT_MIN; for (int x : nums) { cur = max(x, cur + x); best = max(best, cur); } return best; } int minSubArray(const vector<int>& nums) { int cur = 0; int best = INT_MAX; for (int x : nums) { cur = min(x, cur + x); best = min(best, cur); } return best; } int main() { int n; cin >> n; vector<int> nums(n); int total = 0; for (int i = 0; i < n; ++i) { cin >> nums[i]; total += nums[i]; } int mx = maxSubArray(nums); if (mx < 0) { cout << mx << endl; return 0; } int mn = minSubArray(nums); cout << max(mx, total - mn) << endl; return 0; }

验证几个用例：

• [5, -3, 5]：mx = 7，mn = -3，total = 7，max(7, 7 - (-3)) = max(7, 10) = 10，正确。
• [-2, -3, -1]：mx = -1，mx < 0 直接输出 -1，正确（答案是最大的单元素 -1，不能是空数组 0）。
• [1, 2, 3]：mx = 6，mn = 1，total = 6，max(6, 6-1) = 6，正确（最大就是整个数组）。

复杂度 O(n)，空间 O(1)，是这套题里最简单的一题。唯一值得注意的就是全负数特判，如果漏掉，哪怕只有一个全负数的测试点，整题分数全丢。

5. 笔试实战中的常见问题与避坑记录

5.1 我这次踩过的三个典型坑

第一个坑在第一题：我一开始真的想用 BFS 写，理由很简单——看到“网格”两个字反射性就想 BFS，完全忽略了体力消耗是 1 和 2 的差异。直到我构造了一个“短路径但全是施工路段、长路径但全是普通道路”的用例，才发现 BFS 的结果是错的。这个教训说明：看到网格先问自己一句“边权相等吗”，再决定用 BFS 还是 Dijkstra，顺序不能反。

第二个坑在第二题：二分写完后，我发现自己把判断条件写成了 end < start，而题目明明允许 end == start 无缝衔接。手写两个订单 [1,2] 和 [2,3] 验证时才发现答案是漏算的。所有涉及“边界是否可取”的题目，建议都单独构造一个恰好相等边界的用例。这类用例通常也是题目的隐藏测试点，专门用来筛粗心的人。

第三个坑在第三题：全负数特判。我当时先写出了 max(mx, total - mn)，拿 [5, -3, 5] 验证通过后就觉得稳了，随手提交前扫了一眼，突然想到全负数的情况，补上了 if (mx < 0) 这一句。如果没补，[-2, -3, -1] 会输出 0，而正确答案是 -1。这类“边界小但隐蔽”的用例，最好在写解题笔记时就固定下来，形成肌肉记忆。

5.2 一套通用的笔试检查清单

我整理了每次笔试提交前必过的五步检查，照着走能挡掉大部分低级失误：

还有一个很实用的技巧：正式笔试环境没有本地编译器那么多辅助工具，但你可以用最笨的办法验证——自己构造一个小用例，手工模拟一遍，再用代码跑一遍。这个过程花不了三分钟，但能抓住一半以上的逻辑错误。我在第二题的二分边界问题上，就是靠手工模拟三个订单捡回一条命的。

6. 这套真题的横向扩展与复盘方法

6.1 同考点的延伸题目

这三题做完别急着下一套，先横向扩展一下。第一题是网格最短路，那你就把 Dijkstra 的模板吃透后，再去刷带障碍的 BFS、0-1 BFS、分层图最短路、状态压缩 + 最短路这几类变体。出行场景经常出现“最小时间”“最少换乘”这类关键词，本质都是图论最短路。

第二题是带权区间调度，这个模型的应用范围非常广。扩展方向有两个：一是如果订单之间允许抢占（可以中途取消再接别的单），那就变成带权任务调度；二是如果司机有多个，那就变成“K 个司机怎么分配订单收益最大”，这个比单司机版本难一个档次，可以考虑上下界费用流或者状态 DP。但笔试最常考的仍然是你已经掌握的单调度 + DP 模型，别贪多。

第三题的“环形 + 最大子段和”组合，套路固定，记住“正难则反”四个字就够了。类似的延伸有环形链表找环入口、环形数组的最小字典序排列等，但它们考察点不同，不需要强行归为一类。真正值得做的是把最小子段和这个对偶思维迁移到其他题型：比如“删除一段使剩余和最大”“翻转一段使总和最大”，这几题本质上是同一个思想在不同包装下的变体。

6.2 我的复盘模板

每次做完一套真题，我会用一个固定模板记录，包括三块内容：第一块是考点与判断信号，记录“看到什么关键词，应该想到什么算法”；第二块是错误清单，把踩过的坑和对应的反例写下来；第三块是最优解法总结，只写一行式的核心思路，比如第二题就写“按 end 排序 + 二分求前驱 + DP”。

这套方法看起来简单，但坚持下来效果很好。刷题重要的不是数量，而是每一套题是否沉淀出了可迁移的判断力。拿到一道新题时，能快速说出“这题考点是带权区间调度，难点只是二分求前驱”，比背十套模板都更有用。

最后再分享一个小经验：三月底的这场笔试，我做完之后最大的收获不是这三题本身，而是意识到出行类大厂出题很喜欢把业务语义披在经典算法外面。你剥开“司机接单”“地图导航”这些外壳，内核全是教科书里的老朋友们。所以复习的时候别只盯着业务题，把每个经典算法的适用条件和判断信号刻进脑子里，才是应对这类笔试题最可靠的护城河。