前阵子在题库里刷到一道题题名叫《学习轨迹》标签只有一个“贪心”。说实话第一眼看过去我还以为是什么树上拓扑、依赖规划之类的硬核题结果把题面读完之后发现模型特别干净有若干个学习任务每个任务有自己的耗时和截止时间你要决定做哪些任务、按什么顺序做最后在“所有任务都不晚于截止时间”的前提下让完成的任务数量尽可能多并输出一条合法的完成顺序。这其实就是一道特别典型的“反悔贪心”题只是包装了一层“学习轨迹”的外壳。这篇博客就把我从读题到推导、证明、写代码、对拍调试的完整过程都记录下来希望对准备算法竞赛或者面试的朋友有帮助。1. 问题模型与核心切入思路1.1 把“学习轨迹”翻译成数学语言先不急着上手写代码而是把题目抽象一下。现在有 n 个学习任务每个任务有两个关键属性耗时 ( t_i )做这个任务需要连续占用多少时间截止时间 ( d_i )这个任务必须在时刻 ( d_i ) 之前含完成。另外还有一个隐含限制同一时刻只能做一个任务任务一旦开始就不能中途停止必须一次性做完。你可以选择任意多个任务来做也可以跳过某些任务。目标很简单在保证每个被选任务都能按时完成的前提下让完成的任务数量最多。这里“学习轨迹”其实就是最终的任务完成顺序。比如你决定做任务 A、D、C那完成顺序可能是 A → D → C这个顺序就是一条轨迹。题目要求输出这条轨迹本质上就是要求你给出一个合法的、最优的调度方案。1.2 为什么固定一个任务集合时按截止时间排序是最优的假设你已经决定要做某个任务集合 S那么 S 里这些任务按什么顺序做最好答案是按截止时间从小到大排序。这个结论很关键是整个贪心策略的地基。我们用一个简单的交换论证来解释。假设当前有一个执行顺序其中相邻两个任务 i 和 j 是逆序的也就是说 ( d_i d_j )但任务 i 排在任务 j 前面。这时候把它们的顺序交换一下不会让任何任务变晚反而会更好。设这两个任务开始前的累计耗时为 T。原来的顺序是先 i 后 j那么i 的完成时刻是 ( T t_i )j 的完成时刻是 ( T t_i t_j )。因为 j 的截止时间更早所以风险在于 ( T t_i t_j ) 很可能超过 ( d_j )。交换之后变成先 j 后 ij 的完成时刻是 ( T t_j )它比原来的 ( T t_i t_j ) 小所以更安全i 的完成时刻是 ( T t_j t_i )它和原来 j 的完成时刻一样但 i 的截止时间比 j 晚所以也更容易满足。所以任意一个存在逆序对的顺序都可以通过若干次交换变成按截止时间升序的顺序而且不会破坏任何任务的截止约束。换句话说对于一个固定的任务集合按截止时间升序执行就是最优的执行顺序。这一步想明白之后问题就从“排列 选择”简化成了“只选择任务选完之后统一按截止时间排序执行”。1.3 从“选集合”到“逐个加入 反悔”如果只是固定集合问题已经很简单了但集合本身需要选择。直接枚举子集是 ( O(2^n) )完全不可行。我们需要一个能够在扫描过程中不断做决定的方案。一个很自然的想法是把所有任务按截止时间从小到大排序然后从早到晚依次“尝试”加入当前计划。每加入一个新任务如果发现当前计划超时了就从已经选中的任务里删掉一个让计划重新变合法。这种“先加入、超时了再删掉一个”的做法就是反悔贪心。它和普通贪心的区别在于普通贪心一旦决定就不改了而反悔贪心允许你临时反悔把之前某个决定撤销掉。关键是删掉哪一个这就是《学习轨迹》这道题真正的考点。2. 贪心策略推导与正确性证明2.1 扫描过程的核心维护量假设我们已经把任务按截止时间升序排好了。扫描到第 i 个任务时维护两个东西now当前已经选中的所有任务按截止时间升序执行最后一个任务完成所需的累计耗时一个数据结构用来记录当前已选任务中“耗时最大”的任务。每遇到一个新任务 i先不管三七二十一把它加进计划里然后让now t_i。这时候如果now d_i说明新任务排在当前所有已选任务的最末尾也能在自己的截止时间前完成所以当前计划合法继续往下扫描。如果now d_i说明把任务 i 加进来之后至少有一个任务的完成时间来不及了。这时候必须从当前已选任务中删掉一个。因为任务数量目标是要最大化删掉一个之后数量会回到原来的大小但我们刚刚尝试过“加入一个”所以总体数量比原来多 0。我们要做的选择就是删掉哪一个让剩下的集合对后续扫描最有利。2.2 超时之后为什么删“耗时最大”的任务这是整个贪心算法最核心的判断。不妨想一想删掉一个任务之后会发生什么第一已选任务的数量减少 1 第二当前累计耗时now会减少被删任务的耗时t。对于后面的任务来说它们关心什么只关心两件事已经完成了多少个任务以及当前累计耗时还有多少。累计耗时越小后面插入新任务的空间就越大。因此当必须删一个任务时删除耗时最大的那个任务可以让now下降得最多留给后面的余量最大。但这样会不会损失什么比如被删掉的那个任务截止时间特别早后面有一个截止时间更晚的任务被保留了这会不会导致问题不会。因为截止时间更早的任务本身在加入时已经验证过合法了即使删掉它也不会让其他更早的任务变差而保留了截止时间更晚的任务只会在执行顺序上排在更后面对前面任务的完成时间没有任何影响。反过来如果删掉一个耗时较小但截止时间较晚的任务保留耗时最大的任务那么now下降得少而且耗时最大的任务还很占地方显然更不利于后续。我们还可以从“支配”的角度来理解。当被迫要删一个任务时我们面临两个候选方案方案 A 删除耗时最大的任务方案 B 删除另一个任务。方案 A 和方案 B 的任务数量相同但方案 A 的累计耗时更小。由于任务都可以按截止时间升序执行累计耗时更小的方案里每个任务的完成时刻都不会比另一个方案更晚。也就是说方案 A 在可行性上支配了方案 B。所以删除耗时最大的任务一定不会比删除其他任务差。2.3 用“不变量”来总结正确性上面是直观理解如果想让自己更安心可以引入一个不变量来总结。假设扫描完前 i 个任务之后算法维护的集合 S 满足在所有“仅从前 i 个任务中选出、并且能全部按时完成”的集合中S 的任务数最多在任务数最多的所有可行集合中S 的累计耗时最小。初始时 S 为空显然满足。加入新任务 i 后如果直接合法那么任务数增加 1达到理论上界且总耗时是在原最优集合基础上加上 t_i可以论证它仍然是最小总耗时的集合。如果超时了说明想在前 i 个任务中实现比当前任务数多 1 的可行集合是不可能成功的于是我们回到原来的任务数此时为了保持“任务数最多且总耗时最小”必须从当前集合中去掉一个任务。去掉耗时最大的任务得到的集合在同样任务数中总耗时最小不变量继续成立。这个不变量成立意味着算法最终得到的一定是全局最优任务数量最多而且在相同数量下累计耗时最小。这也是为什么它比 DP 更高效但不会比 DP 更差。2.4 几个容易被忽略的细节细节一只检查当前任务的截止时间够不够有人会担心插入新任务后之前那些截止时间更早的任务会不会被影响不会。因为我们始终是按截止时间升序扫描的新插入的任务在最终执行顺序里一定排在所有已有任务之后。它不会改变前面任何一个任务的开始时间所以前面任务的完成时刻不会因为新任务的插入而变大。只要新任务自身在它的截止时间前完成整个集合就合法。细节二删掉的可能就是刚加入的任务如果新任务的耗时特别大比如 ( t_i d_i )那么它一加入就会超时删除耗时最大的任务时删除的可能就是它自己。这相当于“尝试加入后立刻放弃”是完全正常的。这个操作保证了算法不会强行选择一个本身就不可能按时完成的任务。细节三全部任务都无法完成怎么办极端情况下可能每个任务单独做都会超时例如所有任务的 ( t_i d_i )。那么算法会不断地加入、删自己最后堆为空答案为 0。这种情况也要在实现上兼容输出空轨迹即可。3. 代码实现与手工模拟3.1 为什么选大根堆我们需要反复拿到当前已选任务中耗时最大的那个并且还可能随时加入新任务。这个需求恰好是“优先队列”最擅长的。C 里可以用priority_queue默认就是大根堆堆顶是最大值。Python 里heapq是小根堆所以存耗时的时候取负数模拟大根堆。实现时还要注意一点题目最后要求输出轨迹而堆里只能快速拿到最大元素没有办法按截止时间升序输出所有元素。所以我们需要额外维护一个标记数组记录哪些任务在最终集合中。最后再按照一开始排好的截止时间顺序扫描一遍把标记为存活的任务输出这个顺序就是合法轨迹。3.2 C 参考实现#include bits/stdc.h using namespace std; struct Task { long long t; // 耗时 long long d; // 截止时间 int id; // 原始编号 }; int main() { int n; cin n; vectorTask tasks(n); for (int i 0; i n; i) { cin tasks[i].t tasks[i].d; tasks[i].id i 1; } // 核心第一步按截止时间升序排序 sort(tasks.begin(), tasks.end(), [](const Task a, const Task b) { return a.d b.d; }); // 大根堆pair耗时, 编号 priority_queuepairlong long, int pq; vectorchar alive(n 1, 0); long long now 0; for (auto task : tasks) { pq.push({task.t, task.id}); alive[task.id] 1; now task.t; if (now task.d) { auto [mx, id] pq.top(); pq.pop(); alive[id] 0; now - mx; } } vectorint ans; for (auto task : tasks) { if (alive[task.id]) { ans.push_back(task.id); } } cout ans.size() \n; for (int i 0; i (int)ans.size(); i) { cout ans[i] (i 1 (int)ans.size() ? \n : ); } return 0; }这段代码可以直接 AC 常规版本。需要注意now和task.d都用long long因为耗时和截止时间都可能很大累加之后很容易超出int的范围。3.3 Python 参考实现import heapq def main(): n int(input()) tasks [] for i in range(n): t, d map(int, input().split()) tasks.append((d, t, i 1)) tasks.sort() # 按截止时间 d 升序 heap [] # 大根堆存 (-耗时, 编号) alive [False] * (n 1) now 0 for d, t, idx in tasks: heapq.heappush(heap, (-t, idx)) alive[idx] True now t if now d: neg_t, idx2 heapq.heappop(heap) alive[idx2] False now - -neg_t ans [idx for _, t, idx in tasks if alive[idx]] print(len(ans)) print(*ans) if __name__ __main__: main()Python 版本里heapq默认是小根堆所以存-t取出时再取负得到真实耗时。整体逻辑和 C 一致。3.4 手工模拟一个完整样例用下面这组数据来走一遍流程任务编号耗时 t截止时间 d134225316447528排序后顺序就是 1、2、3、4、5。一开始now 0堆为空。处理任务 1加入now 33 4合法。堆里现在是{3}。处理任务 2加入now 55 5合法。堆里是{3, 2}。处理任务 3加入now 66 6合法。堆里是{3, 2, 1}。处理任务 4加入now 1010 7超时。此时堆顶是任务 4耗时 4所以把任务 4 删掉now 10 - 4 6。堆里剩下{3, 2, 1}。处理任务 5加入now 88 8合法。堆里现在是{3, 2, 2, 1}。最终堆中有 4 个任务分别是任务 1、2、3、5。按截止时间顺序输出就是1 2 3 5。验证一下任务 1完成于时刻 3截止 4合法任务 2完成于时刻 5截止 5合法任务 3完成于时刻 6截止 6合法任务 5完成于时刻 8截止 8合法。所以最优轨迹就是 1 → 2 → 3 → 5答案 4。这里可以看到任务 4 虽然截止时间晚但耗时太长如果把它留下就必须删掉任务 1最终总耗时反而更大。算法选择删除耗时最大的任务其实是在为后续任务留出更多空间。4. 常见问题与调试实录4.1 排序的第二关键字要不要处理很多实现里只按截止时间升序排序相同截止时间的任务顺序任意。这不会影响答案因为反悔贪心最终选出的集合和数量是一样的。不过有一个小细节如果相同截止时间耗时大的任务放在前面可能会导致它加入后又立刻被删掉多一次堆操作如果把耗时小的放在前面操作会少一点。但复杂度上都是 (O(n \log n))差别不大。我有一次在本地对拍时发现两种排序得到的轨迹编号不一样但答案数量和可行性完全一致后来想明白是因为存在多个最优解。如果你希望输出稳定可以在排序时第二关键字按耗时升序或按编号升序这样轨迹确定。4.2 为什么扫描时只判断now d[i]就够了这个问题我在学习的时候困惑了很久。因为当前已选任务里可能有截止时间比d[i]更早的任务如果now变大了会不会导致那些更早截止的任务超时答案是不会。因为在扫描过程中已选任务始终按截止时间升序排列新加入的任务一定排在末尾。更早的任务完成时刻不会因为后面插入新任务而改变。它们在自己被加入的那个时刻已经验证过合法了所以后续只需要检查新加入的这个最晚截止任务即可。这个性质是“按截止时间排序”带来的红利。如果一开始没有排序这里的正确性就不成立了。4.3 堆空时能不能pop代码里只有在now d[i]时才进入pop而这时刚刚push了当前任务所以堆一定不为空。不要在最外层写一个“如果堆非空才 pop”之类的逻辑那样反而可能掩盖真正的问题。我见过有人这样写if (now d) { if (!pq.empty()) { ... } }这个写法虽然不会 RE但会掩盖一个逻辑漏洞如果堆是空的说明之前已经出错了不该继续往下跑。正确的做法是在该删除的时候堆一定非空直接pop就好。4.4 输出轨迹时“堆里有什么”不等于“顺序是什么”这是我第一次写这个题时犯的错。我直接把堆里剩下的任务编号pop出来当作轨迹结果顺序完全乱。因为堆只保证能快速取出最大耗时元素并不维护截止时间顺序。正确的输出方式有两种用alive标记数组最后再遍历一次按截止时间排好的任务数组输出存活任务的编号或者把所有存活任务的编号收集后重新按照这些任务原来的截止时间排序再输出。第一种更简单也更好调试。记住你维护“当前集合”用的是堆但输出“轨迹”时要回到有序数组。4.5 用 DP 对拍验证贪心为了确保贪心算法不是碰巧过样例我写了一个 (O(n^2)) 的 DP 用来对拍。DP 的状态设计令dp[j]表示“处理完当前前缀完成 j 个任务所需的最小累计耗时”并且保证这 j 个任务按截止时间升序排列时都合法。初始dp[0] 0其余为无穷大。按截止时间升序遍历每个任务对每个任务做反向更新vectorlong long dp(n 1, LLONG_MAX / 4); dp[0] 0; for (auto task : tasks) { long long t task.t, d task.d; for (int j n; j 1; j--) { if (dp[j - 1] t d) { dp[j] min(dp[j], dp[j - 1] t); } } }最终最大的j满足dp[j] INF就是最优任务数。这个 DP 的理解方式dp[j - 1]是完成前 j-1 个任务的最小耗时把当前任务作为第 j 个任务放到底只要dp[j - 1] t d就说明它能在截止时间前完成。反向更新保证每个任务最多被选一次。对拍时随机生成小规模数据分别跑贪心和 DP比较答案数量、合法性、以及最终输出轨迹是否确实不超时。跑了几万组之后我才敢确信这个贪心是对的。5. 扩展从“任务数量”到“加权收益”5.1 带权任务调度的堆解法《学习轨迹》只要求最大化任务数量。如果把条件改成“每个任务还有一个收益 ( w_i )目标是总收益最大”那删除策略就要变了。此时按截止时间排序的思路不变但超时后要删除的是“收益最小”的任务而不是耗时最大的任务。具体做法是维护一个小根堆堆内存当前已选任务的收益。每次尝试加入新任务累加总耗时如果超时就从堆里弹出收益最小的任务并从总耗时里减去它的耗时。这样可以保证在相同总耗时限制下保留的收益尽可能大。这个模型非常经典很多任务调度题都是它的变体。5.2 “学习总时长最长”与“数量最多”的差别如果题目问的不是“最多能完成几个任务”而是“在合法前提下最多能累计学习多长时间”那又是另一种趣味。这时候每个任务的收益就是它的耗时本身。用带权调度的方法超时时删除收益最小的任务也就是删除耗时最短的任务。你会发现这个策略和“数量最多”恰好相反一个努力留下耗时短的任务一个努力留下耗时长但价值高的任务。同样是反悔贪心不同的优化目标导致不同的删除优先级。这个对比非常值得自己推一遍能加深对“反悔贪心核心在于维护不变量”的理解。5.3 更进一步的学习建议如果你把《学习轨迹》吃透了可以继续看这些方向带截止时间、耗时和收益的通用调度问题核心是排序 堆多台机器并行学习的变体需要用多个堆或者可撤销堆来维护依赖关系下的学习路径规划那就要结合拓扑排序、树形 DP 甚至反悔贪心一起考虑。算法竞赛里很多题都是这样表面上是“轨迹”“路径”“规划”剥开之后底层是一个经典模型。学会从题目包装里找到核心矛盾比背某个特定解法重要得多。6. 一点个人经验这种“排序 反悔删除”的贪心题我踩过最多次的坑不是想不到堆而是没有想清楚“删除哪个”背后的优化目标。只看任务数量时删除耗时最大看总收益时删除收益最小。不要死记一定要从“删除一个任务后对后续状态有什么影响”出发去推导。如果你也正在学贪心我建议拿到一道调度题先别急着写代码先回答三个问题第一固定选择集合后最优执行顺序是什么第二当前维护的状态里哪个量决定了后面的可行性第三被迫放弃一个任务时放弃标准应该是什么这三个问题想明白代码只是最后一步。最后分享一个调试小技巧写对拍的时候不要只比较答案数量还要把贪心输出的轨迹真正模拟执行一遍逐个检查每个任务的完成时间是否小于等于截止时间。很多反悔贪心实现看起来答案对但轨迹是错的问题往往出在输出顺序上。用alive标记数组从有序数组里收集答案是最稳妥的方式。