企业官网建设流程全解析

距离美团2023校招技术岗第9场笔试结束已经有一段时间，但三道题当时带给我的冲击感到现在还记得。这场笔试的题面几乎每一道都套了一层业务壳：骑手怎么接单、门店评分怎么调、配送站点上的包裹怎么取。剥开壳之后你会发现，考的全是算法题里最常被忽略的底层模型——贪心加反悔堆、差分数组、树上依赖背包。这篇文章把这三道题完整地复盘了一遍，既给出了我能跑通的实现，也把推导过程中的关键想法和踩坑点一起写了出来。不管你是正在备战校招的应届生，还是想补一补算法基础的工程师，这套题都值得认真过一遍。

1. 第9场笔试的整体印象：三题分布与美团出题口味

1.1 题量、时长与难度梯度

这场笔试我记忆里是120分钟三道题，全部是ACM风格的输入输出，也就是你得自己处理标准输入、自己输出结果。第一题只要掌握贪心加一个优先队列就能拿下，但前提是你得意识到"直接按截止时间排队"这个朴素做法是错的。第二题考的是差分数组，如果你没见过这类模型，很容易把问题想复杂，甚至去写线段树，然后越写越慌。第三题是树上依赖背包，难度直接拉满，我身边能当场AC的人不多，大多数人是暴力枚举部分用例拿分。

从分值分布来看，三题的分值并不是平均的，越往后分值占比越大。这意味着即便前两题全对，第三题只过一半用例，总分也可能被拉开很远。美团笔试的系统是按通过用例数给分的，所以能拿部分分一定要拿，空题是零分，暴力骗分不丢人。

1.2 美团出题的一个明显偏好：业务壳很厚

这三道题没有一道是直接说"给你一个数组，请做某某操作"，也没有"请默写最短路模板"。每道题都包了一层业务场景：骑手配送、门店经营调整、配送网络取件。这是美团出题的一贯风格，也可以理解为面向业务的技术团队在筛选候选人时的价值取向——算法能力强，同时也要能快速把业务问题翻译成数学模型。

我经常跟准备校招的朋友说，看到这种"故事很长、数据范围写在最后"的题目，第一件事不是逐字读故事，而是先扫一眼数据范围，再找题目最后那句"求什么"。数据范围直接告诉你复杂度上限，求什么决定算法方向。这两个信息拿到手，场景描述里的大部分话术就可以暂时忽略。

1.3 横向对比：第9场相比其他场次难在哪

网上能搜到的其他场次题目，有些第一题就是普通数组操作、字符串判断，第二题是二叉树层序遍历，第三题是最短路或并查集。第9场这场不一样，第一题就不是纯送分，而是"朴素贪心选不出来、需要反悔"的经典模型；第二题如果没听过差分，会卡很久；第三题又把树形DP和背包结合，三个知识点叠在一起。

从我复盘的角度看，这套题的区分度设计得相当好。它没有考冷门算法，考的全是高频模型，但高频模型嵌套到业务场景里，难度立刻上一个台阶。而且三道题的模型几乎没有重复，覆盖了贪心、差分、树DP三个方向，基本把校招算法笔试的主干考了个遍。

2. 第一题：先送哪单不超时，堆加贪心才是正解

2.1 还原后的题面

某外卖平台有 n 个待配送订单，第 i 个订单骑手需要耗时 time_i 才能完成配送，用户期望在 deadline_i 时刻之前（含）收到餐。骑手一次只能配送一个订单，两个订单之间切换不耗时，骑手从 0 时刻开始工作。请计算骑手最多能让多少个订单按时送达。

输入：第一行一个整数 n（1 <= n <= 100000）。接下来 n 行，每行两个整数 time_i 和 deadline_i（1 <= time_i, deadline_i <= 1e9）。

输出：一个整数，表示最多能按时送达的订单数。

刚看到这个题时，我的第一反应是"这不就是按截止时间排序然后顺序做吗"。但构造一个反例就能推翻：订单 A 耗时 3、截止 4；订单 B、C、D 各耗时 1、截止 5。按截止时间排序后，A 排在前面，如果先做 A，到时刻 3 完成，后面只有 B 能在时刻 4 完成，C、D 都超时，最多 2 单。但如果你跳过 A，先做 B、C、D，三个都能在截止时间内完成，最多 3 单。

这个反例说明了一个关键结论：这类调度问题里，单纯按截止时间贪心不够，因为"先做的订单"可能会挤掉后面多个更短的订单。我们需要在决策过程中允许反悔——把已经选中的、耗时最长的订单踢出去，给后面更优的订单腾位置。

2.2 最大堆替换法的推导与证明

正确做法分两步。第一步，把所有订单按 deadline 从小到大排序。第二步，维护一个"已选订单耗时"的大根堆，同时维护当前已选订单的总耗时 cur。每扫描到一个新订单，先把它的耗时 t 入堆、cur 加上 t；如果此时 cur 已经超过了当前订单的 deadline，就把堆里耗时最大的订单移出，cur 减去该耗时。

为什么第一步要按截止时间排序？因为我们每一步都在考虑"截止时间最早的订单"，希望优先满足时间压力更大的订单；而反悔操作保证了已经选中的集合始终是在"前 k 个订单里，能按时完成且总耗时最小"的集合。换句话说，扫描到第 i 个订单时，堆里的集合就是"前 i 个订单中，最多能按时完成的那一组，且该组总耗时是所有同等数量方案里最小的"。这个不变量是整个反悔贪心正确性的基石。

为什么踢掉最大的就是对的？因为踢掉一个耗时大的订单，cur 的下降量最大，腾出的时间最多，能容纳后续更多订单；而总订单数在"先加入再删除"的过程中保持不变，只换不增，所以不会因为"踢错了"导致数量减少。这个技巧在很多文章里叫反悔堆，在力扣上对应"课程表 III"这道题，本质上是同一个模型。只要你能把这个模型和外卖配送场景对应上，代码就是十分钟的事。

2.3 边界情况与复杂度分析

所有数字都是正整数，所以不需要考虑 0 时刻和负截止时间。n 最大是 1e5，排序 O(n log n)，堆操作每个订单入堆出堆最多一次，总复杂度 O(n log n)，空间 O(n)。这里有个容易忽略的点：cur 要用 long long，虽然单个 time_i 只有 1e9，但 n 个累计起来会超过 2^31-1，int 溢出后 cur 可能变负数，判断cur > deadline会直接失灵。这个坑我在考场踩过，后来凡是累计求和的变量，一律 long long 起步。

2.4 可运行的实现代码

#include <bits/stdc++.h> using namespace std; int main() { int n; scanf("%d", &n); vector<pair<long long, long long>> a(n); // first: deadline, second: time for (int i = 0; i < n; i++) { scanf("%lld%lld", &a[i].second, &a[i].first); } sort(a.begin(), a.end()); priority_queue<long long> pq; // 大根堆 long long cur = 0; for (auto &p : a) { long long t = p.second; pq.push(t); cur += t; if (cur > p.first) { cur -= pq.top(); pq.pop(); } } printf("%zu\n", pq.size()); return 0; }

这个题用 Python 写也很简单，但要注意heapq默认是小根堆，想取最大值要么存负数，要么用heapq.nlargest再手动改，写法上比 C++ 烦一点。笔试时如果输入规模大，Python 的heappush和heappop是 O(log n)，1e5 的数据也能过，不用担心超时