如果你也正被这个“飞机降落问题”卡住提交结果只显示两项案例通过先别急着怀疑人生。这道题我当年也栽过本地样例怎么跑怎么对逻辑读一遍没毛病可提交后就是过不了几个测试点。后来花了一晚上逐层打日志才发现问题根本不在“会不会回溯”而在几处特别容易忽略的时间边界。这篇文章把这道题的完整解法和排查思路写下来希望能帮同样卡住的人少走点弯路。1. 别急着改代码先确认你理解的是哪个“飞机降落问题”1.1 题面在说什么一个机场调度模型飞机降落问题的题面通常长这样有 n 架飞机第 i 架有一个到达时间 t一个可盘旋时间 d一个降落占用跑道时间 l。飞机可以在到达后的任意时刻开始降落但不能晚于 td而且开始降落的时间不能早于 t。跑道同一时间只能服务一架飞机。问是否存在一个降落顺序让所有飞机都能成功落地。很多人把“可盘旋时间”理解成“可以一直等到 d 分钟、然后在任意时刻降落完成”这是第一个误区。盘旋时间的真正含义是飞机最多只能在空中多等 d 分钟所以它最晚的开始降落时间是 td而不是说降落过程必须在 td 前结束。放在只有一个工位的汽车维修铺里理解会更直观每辆车有一个最早到店时间 t顾客最多愿意等到 td维修要占工位 l 分钟。老板能不能把这批顾客全服务完问题抽象后唯一要决策的就是每个顾客飞机的进店顺序。飞机晚到没关系只要在顾客离开前开始维修就行。1.2 代码里最容易错的三个“窗口边界”先说第一架飞机的处理。很多人的回溯函数里代表“跑道空闲时间”的变量 last 初始化为 0这本身没错但第一架飞机如果到达时间很晚比如 t100跑道从 0 开始就空着飞机实际能开始降落的时间是 100 而不是 0。所以下一架飞机的开始时间必须写成 max(last, t[i])而不是直接用 last 或 t[i]。一旦你写成了 last l[i]就会把第一架飞机“凭空提前”后面的状态全是错的。再说窗口判断。合法条件应该是long long start max(last, t[i]); if (start t[i] d[i]) continue; // 不合法错过最晚开始时间注意这里比较的是开始时间 start不是完成时间。我给你一个反例t0, d5, l6。如果写成了last l[i] t[i] d[i]来判断last0 时 066 5会判成不合法但实际上飞机在 0 时刻开始降落6 时刻完成完全在允许范围内。这个错法非常隐蔽因为样例里很少给这种“窗口很短但降落很长”的数据。第三个坑是数据溢出。t 和 d 的范围如果达到 1e9 量级td 用 int 存会溢出成负数。一旦溢出你的start t[i] d[i]判断就会乱掉可能永远为 true也可能永远为 false。这类题提交时经常有超大边界数据所以时间相关变量一律用 long long不要心存侥幸。1.3 回溯代码里的变量语义要统一我在调试这道题时最大的体会是变量名一定要能准确表达语义。我常用的三个变量是// runwayFree: 跑道上一架飞机完成、重新空闲的时刻 // start: 当前飞机实际开始降落时刻 // finish: 当前飞机完成降落的时刻 // start max(runwayFree, t[i]) // 合法条件: start t[i] d[i] // finish start l[i]写回溯时递归函数里只需要传两个信息已经安排了多少架飞机 pos以及当前跑道最早空闲时间 runwayFree。下一层递归调用时传入 finish也就是 start l[i]。这样整个搜索的状态转移是确定的不会因为变量混用而出现“这次用 last下次用 finish”的错乱。把三个变量的语义写在注释里调 bug 的速度能快一半。很多人的代码只过两个案例就是因为在递归里把“开始时间”和“结束时间”混着用样例碰巧能跑通一上边界数据就露馅。2. 为什么你的代码只能过两项案例四个高频雷区2.1 状态回溯不完整篡改现场却忘了恢复回溯算法的核心是“尝试-递归-撤销”。最常见的错误是递归返回 false 后忘了把 vis[i] 重新置为 false。看下面这段有问题的代码bool dfs(int pos, long long last) { if (pos n) return true; for (int i 0; i n; i) { if (!vis[i]) { long long start max(last, t[i]); if (start t[i] d[i]) continue; vis[i] true; if (dfs(pos 1, start l[i])) return true; // 这里忘写 vis[i] false; } } return false; }这段代码在单组样例下可能表现正常因为第一个分支如果恰好成功整个程序就结束了根本不需要撤销。但一旦第一组数据需要回溯或者有多组测试样例vis 数组就会被上一次搜索污染导致后面的分支认为所有飞机都已经降落了直接返回 false。正确的写法是只要 dfs 返回 false就必须在本层撤销选择。注意如果 dfs 返回 true 就不需要撤销因为程序已经找到答案并开始返回了。这个细节背下来容易但调试时真的很致命。另外多组样例输入时每组的 vis 数组一定要重置。很多人只重置了 n忘了重置 vis导致第二组样例一开始就有飞机被标记为“已降落”结果当然只能过第一个样例。2.2 对“最晚开始时间”的错误理解我见过三种典型的错误理解每种都能让你的代码只过部分用例。第一种是把 td 当成“降落完成的最晚时间”。假设 t0, d5, l6飞机在 0 时刻开始降落6 时刻完成。如果代码用last l[i] t[i] d[i]做判断06 5直接判不合法。但事实上这架飞机完全来得及。所以判断条件必须针对开始时间而不是完成时间。第二种是忽略了飞机到达时间的约束。有些简化写法只判断last t[i] d[i]然后认为只要跑道足够早空闲就能安排。可如果 t[i] 本身很大比如 last0, t100, d0跑道确实空闲但飞机要等到 100 才能开始降落而它最晚开始时间也是 100表面上看 last0 没有超过 100似乎合法。实际上用 max(0,100)100 来判断100 100恰好合法。但如果你把 start 写成了 max(last, 0) 或者直接用 last就会错误地认为这架飞机可以在 0 时刻开始导致后续调度全部提前。必须用 max(last, t[i]) 来算 start。第三种是觉得飞机必须按照到达时间排序于是先按 t 排序再线性扫描判断。这个思路看似有道理但忽略了“晚到的飞机可以先占用跑道”的可能性。比如飞机 A 到达时间为 0、盘旋 10 分钟、降落耗时 10 分钟飞机 B 到达时间为 5、盘旋 0 分钟、降落耗时 1 分钟。如果按到达时间先安排 AA 从 0 到 10 占着跑道B 只能在 10 开始但 B 最晚开始时间是 5所以线性判断会误判为不可能。其实 B 先降落后 A 再降落才可行。这就说明这道题必须搜索所有排列顺序任何“先排序再贪心”的思路都可能出错。2.3 long long 与输入解析阴沟里翻船这类数据结构的题输入量通常不大但数值范围可能很大。我之前就因为 int 溢出吃过亏t1e9, d1e9td2e9int 最大值是 2147483647按说没有溢出但如果 t 和 d 都取 1e9 稍微多一点就会超。更稳妥的做法是全程使用 long long并且读入时直接读到 long long 变量里。还有一个小细节如果你混用 cin 和 scanf又关闭了同步流可能会导致读入顺序错乱。n 比较小的时候老老实实用 cin 就行或者统一用 scanf/printf。我见过有人在循环里先 scanf 读 n再用 cin 读三个数关掉 ios::sync_with_stdio(false) 之后第二组数据直接读不出来提交时只过前两个样例就超时或读入失败。2.4 只跑一遍样例就提交遗漏隐藏边界很多人拿到题样例能过就立刻提交然后盯着“两项案例通过”发呆。要知道样例通常只给最普通的场景隐藏测试点会覆盖这些要命的情况飞机数量为 1而且 d 为 0。所有飞机的降落窗口完全错开可以无缝衔接。有一架飞机窗口非常短必须在最后安排。某一架飞机到达时间特别晚导致前面所有飞机都要等它。这些边界其实都可以在本地提前构造验证。别急着提交先花五分钟把自己能想到的极端情况写成测试用例跑一遍再交。这一个习惯能让你的通过率立刻提升一大截。3. 一个能稳定 AC 的写法回溯框架与可选优化3.1 标准回溯版数据量小的时候直接过这类题通常数据范围给得很保守n 不超过 1010! 的排列也就 3628800 种回溯加上剪枝完全够用。下面是我推荐的标准写法直接抄就能用#include bits/stdc.h using namespace std; typedef long long ll; int n; ll t[15], d[15], l[15]; bool vis[15]; bool dfs(int pos, ll runwayFree) { if (pos n) return true; // 所有飞机都已安排完 for (int i 0; i n; i) { if (vis[i]) continue; ll start max(runwayFree, t[i]); // 跑道空闲时间和飞机到达时间取较晚 if (start t[i] d[i]) continue; // 错过了最晚开始时间直接剪掉 vis[i] true; if (dfs(pos 1, start l[i])) return true; vis[i] false; // 回溯撤销选择 } return false; } int main() { int T; cin T; while (T--) { cin n; for (int i 0; i n; i) { cin t[i] d[i] l[i]; } memset(vis, 0, sizeof vis); if (dfs(0, 0)) cout YES\n; else cout NO\n; } return 0; }这个代码的核心就两行一行算 start一行判断 start 是否在窗口内。看到max(runwayFree, t[i])千万不要简化成runwayFree因为飞机晚到时跑道早早就空出来了但飞机还没到实际开始时间必须等飞机到达。同样不能简化成t[i]因为跑道可能还忙着必须等上一架完成。3.2 三个减少无效分支的实用技巧如果你的数据范围稍微大一点n 到 15 左右纯回溯可能有点吃力可以尝试下面三个技巧。先说最简单的跳过完全重复的飞机。如果两架飞机的 t、d、l 完全相同在当前状态下先尝试哪一架效果一样。如果第一架尝试失败第二架也没必要再试。实现方式可以先把飞机按参数排序然后在循环里加一个判断如果当前飞机和上一架参数完全相同并且上一架还没被访问说明上一架已经尝试过且失败直接 continue。第二个技巧是状态压缩 DP。n 不超过 20 时可以用dp[mask]表示已经安排完 mask 集合内所有飞机后跑道最快的空闲时间。由于跑道空闲时间越早越有利于后续安排所以每个集合只保留最小的完成时间即可。转移时枚举下一个要安排的飞机 i判断它能否在窗口内开始降落然后更新新状态ll dp[1 20]; dp[0] 0; for (int mask 0; mask (1 n); mask) { if (dp[mask] INF) continue; for (int i 0; i n; i) { if (mask (1 i)) continue; ll start max(dp[mask], t[i]); if (start t[i] d[i]) continue; dp[mask | (1 i)] min(dp[mask | (1 i)], start l[i]); } }这个 DP 比回溯稳得多因为它天然避免了重复状态的搜索而且转移条件极其清晰。如果你只是在做练习建议两种写法都写一遍对理解“状态压缩”和“回溯剪枝”的区别非常有帮助。第三个技巧是搜索顺序优化。在回溯的每一层优先尝试当前 start 最小的飞机可以更快地找到可行解或者在找不到解时更快地触发剪枝。但这只是一个启发式优化不保证一定比固定顺序快也不建议在没搞懂回溯原理之前去依赖它。对于 n≤10完全没必要。3.3 构造自己的边界测试轮我最推荐的做法是在提交之前先构造一组边界用例确保代码能正确响应。下面这些用例基本覆盖了常见的隐藏测试点测试用例预期结果说明n1, t0, d0, l10YES单架飞机且不允许盘旋n1, t5, d3, l10YES开始时间为5完成15完全合法n2, 飞机A: 0 0 10, 飞机B: 5 10 1YES必须安排A先降落B可以等n2, 飞机A: 0 0 10, 飞机B: 5 0 1NOB窗口很短但A占着跑道反之A等不了n3, 三架飞机窗口依次错开0 0 1, 1 0 1, 2 0 1YES标准流水线n3, 三架飞机都在同一时间到达视降落时间而定检查所有排列构造用例时我习惯用一个简单的原则每架飞机都设计一个“窗口结束前最后一刻才开始降落”的场景看看代码会不会误判。比如 t0, d5, l6 这种用例如果代码用完成时间做判断一定出错。把这些用例在本地跑一遍再提交基本就能避开“样例过了但隐藏用例挂掉”的尴尬。4. 现场排查实录与调试心得4.1 用打印回溯现场找坏点调这类题最有效的方法是在 dfs 函数里加打印观察每次尝试的状态。我已经养成习惯在进入循环前打印当前 pos 和 runwayFree在每次选中一架飞机后打印“尝试第 i 架startxxxfinishxxx”。日志长这样进入 dfs, pos0, runwayFree0 尝试第0架, t0, d5, l6, start0, finish6 进入 dfs, pos1, runwayFree6 尝试第1架, t5, d0, l1, start6, finish7如果发现某一步 start 明显小于 t[i]说明 max 写漏了如果某一步明明 start t[i]d[i] 但代码还是继续递归说明判断条件写错了。打印日志之后错误点几乎一眼就能看出来。调试完记得把打印注释掉否则大量输出会导致超时。4.2 我的两个阴间 Bug 复盘我第一次做这道题只过了两个案例查了一晚上才发现两个问题。第一个是把转移公式写成了start max(runwayFree, t[i]) l[i]然后在递归里传入了 start这就把“开始时间”和“完成时间”混在了一起。逻辑上下一架飞机的跑道空闲时间应该是上一架的完成时间而我把它写成了当前飞机的开始时间。结果所有后续窗口都被提前样例又恰好没有触发这种错误提交就只过了一项。这个教训告诉我变量的命名必须和实际含义一一对应不能为了省变量名就随便复用。第二个更蠢判断条件写成了if (runwayFree t[i] d[i]) continue;漏掉了 max。当跑道空闲时间远早于飞机到达时间时runwayFree 看起来没有超过最晚开始时间但飞机其实已经错过了自己的窗口。比如跑道 0 时刻就空了飞机 100 时刻才到d0跑道空闲时间确实不大于 100但这架飞机在 100 时刻才到达而最晚开始时间也是 100虽然能赶上但如果 d0 会错。这个坑的教训是判断窗口时必须比较“实际开始时间”和“最晚开始时间”而实际开始时间是跑道空闲时间和到达时间的较大者。4.3 交之前先做的三件事根据我的经验提交前做下面三件事能大幅提高通过率第一写一个全排列暴力版本和数据量不大时的回溯版本对拍。暴力版本直接枚举所有排列顺序检查是否可行。随机生成几百组数据只要两个版本结果不一致就说明回溯代码有隐蔽逻辑错误。对拍是排查回溯问题最可靠的方法没有之一。第二检查所有用于时间计算的变量类型。把所有 t、d、l、start、finish 全部定义为 long long绝对不要用 int。就算题目说数据范围小也建议用 long long因为代码以后复用起来更安全。第三确认多组样例之间的状态清理。重点看 vis 数组是否每轮都重置全局变量 n 是否被覆盖以及读入操作是否在每组样例开始前正确执行。这三类错误在所有回溯题里都是高频事故飞机降落问题也不例外。最后分享一点个人经验我后来重新审视这道题发现它考的不是“会不会写递归”而是“能不能把一个动态过程里的每个时间点都搞清楚”。机场调度模型其实非常贴近现实你既要尊重飞机到达时间又要考虑跑道占用还要理解每架飞机愿意等待的极限。把这三个要素拆开按照“实际开始时间 max(跑道空闲, 飞机到达)”这个公式一步步推代码自然就对了。如果你现在还卡在“只能通过两项案例”先把判断条件和转移公式抄在纸上逐行模拟一遍再打开代码对比。大部分问题都出在那一两个max和 l[i]上。改完之后记得把边界测试轮跑一遍再提交。这道题值得你多花一点时间因为回溯状态恢复和窗口判断的技巧在别的调度类题目里还会反复出现。
飞机降落问题：回溯算法、窗口判断与边界调试全解析
如果你也正被这个“飞机降落问题”卡住提交结果只显示两项案例通过先别急着怀疑人生。这道题我当年也栽过本地样例怎么跑怎么对逻辑读一遍没毛病可提交后就是过不了几个测试点。后来花了一晚上逐层打日志才发现问题根本不在“会不会回溯”而在几处特别容易忽略的时间边界。这篇文章把这道题的完整解法和排查思路写下来希望能帮同样卡住的人少走点弯路。1. 别急着改代码先确认你理解的是哪个“飞机降落问题”1.1 题面在说什么一个机场调度模型飞机降落问题的题面通常长这样有 n 架飞机第 i 架有一个到达时间 t一个可盘旋时间 d一个降落占用跑道时间 l。飞机可以在到达后的任意时刻开始降落但不能晚于 td而且开始降落的时间不能早于 t。跑道同一时间只能服务一架飞机。问是否存在一个降落顺序让所有飞机都能成功落地。很多人把“可盘旋时间”理解成“可以一直等到 d 分钟、然后在任意时刻降落完成”这是第一个误区。盘旋时间的真正含义是飞机最多只能在空中多等 d 分钟所以它最晚的开始降落时间是 td而不是说降落过程必须在 td 前结束。放在只有一个工位的汽车维修铺里理解会更直观每辆车有一个最早到店时间 t顾客最多愿意等到 td维修要占工位 l 分钟。老板能不能把这批顾客全服务完问题抽象后唯一要决策的就是每个顾客飞机的进店顺序。飞机晚到没关系只要在顾客离开前开始维修就行。1.2 代码里最容易错的三个“窗口边界”先说第一架飞机的处理。很多人的回溯函数里代表“跑道空闲时间”的变量 last 初始化为 0这本身没错但第一架飞机如果到达时间很晚比如 t100跑道从 0 开始就空着飞机实际能开始降落的时间是 100 而不是 0。所以下一架飞机的开始时间必须写成 max(last, t[i])而不是直接用 last 或 t[i]。一旦你写成了 last l[i]就会把第一架飞机“凭空提前”后面的状态全是错的。再说窗口判断。合法条件应该是long long start max(last, t[i]); if (start t[i] d[i]) continue; // 不合法错过最晚开始时间注意这里比较的是开始时间 start不是完成时间。我给你一个反例t0, d5, l6。如果写成了last l[i] t[i] d[i]来判断last0 时 066 5会判成不合法但实际上飞机在 0 时刻开始降落6 时刻完成完全在允许范围内。这个错法非常隐蔽因为样例里很少给这种“窗口很短但降落很长”的数据。第三个坑是数据溢出。t 和 d 的范围如果达到 1e9 量级td 用 int 存会溢出成负数。一旦溢出你的start t[i] d[i]判断就会乱掉可能永远为 true也可能永远为 false。这类题提交时经常有超大边界数据所以时间相关变量一律用 long long不要心存侥幸。1.3 回溯代码里的变量语义要统一我在调试这道题时最大的体会是变量名一定要能准确表达语义。我常用的三个变量是// runwayFree: 跑道上一架飞机完成、重新空闲的时刻 // start: 当前飞机实际开始降落时刻 // finish: 当前飞机完成降落的时刻 // start max(runwayFree, t[i]) // 合法条件: start t[i] d[i] // finish start l[i]写回溯时递归函数里只需要传两个信息已经安排了多少架飞机 pos以及当前跑道最早空闲时间 runwayFree。下一层递归调用时传入 finish也就是 start l[i]。这样整个搜索的状态转移是确定的不会因为变量混用而出现“这次用 last下次用 finish”的错乱。把三个变量的语义写在注释里调 bug 的速度能快一半。很多人的代码只过两个案例就是因为在递归里把“开始时间”和“结束时间”混着用样例碰巧能跑通一上边界数据就露馅。2. 为什么你的代码只能过两项案例四个高频雷区2.1 状态回溯不完整篡改现场却忘了恢复回溯算法的核心是“尝试-递归-撤销”。最常见的错误是递归返回 false 后忘了把 vis[i] 重新置为 false。看下面这段有问题的代码bool dfs(int pos, long long last) { if (pos n) return true; for (int i 0; i n; i) { if (!vis[i]) { long long start max(last, t[i]); if (start t[i] d[i]) continue; vis[i] true; if (dfs(pos 1, start l[i])) return true; // 这里忘写 vis[i] false; } } return false; }这段代码在单组样例下可能表现正常因为第一个分支如果恰好成功整个程序就结束了根本不需要撤销。但一旦第一组数据需要回溯或者有多组测试样例vis 数组就会被上一次搜索污染导致后面的分支认为所有飞机都已经降落了直接返回 false。正确的写法是只要 dfs 返回 false就必须在本层撤销选择。注意如果 dfs 返回 true 就不需要撤销因为程序已经找到答案并开始返回了。这个细节背下来容易但调试时真的很致命。另外多组样例输入时每组的 vis 数组一定要重置。很多人只重置了 n忘了重置 vis导致第二组样例一开始就有飞机被标记为“已降落”结果当然只能过第一个样例。2.2 对“最晚开始时间”的错误理解我见过三种典型的错误理解每种都能让你的代码只过部分用例。第一种是把 td 当成“降落完成的最晚时间”。假设 t0, d5, l6飞机在 0 时刻开始降落6 时刻完成。如果代码用last l[i] t[i] d[i]做判断06 5直接判不合法。但事实上这架飞机完全来得及。所以判断条件必须针对开始时间而不是完成时间。第二种是忽略了飞机到达时间的约束。有些简化写法只判断last t[i] d[i]然后认为只要跑道足够早空闲就能安排。可如果 t[i] 本身很大比如 last0, t100, d0跑道确实空闲但飞机要等到 100 才能开始降落而它最晚开始时间也是 100表面上看 last0 没有超过 100似乎合法。实际上用 max(0,100)100 来判断100 100恰好合法。但如果你把 start 写成了 max(last, 0) 或者直接用 last就会错误地认为这架飞机可以在 0 时刻开始导致后续调度全部提前。必须用 max(last, t[i]) 来算 start。第三种是觉得飞机必须按照到达时间排序于是先按 t 排序再线性扫描判断。这个思路看似有道理但忽略了“晚到的飞机可以先占用跑道”的可能性。比如飞机 A 到达时间为 0、盘旋 10 分钟、降落耗时 10 分钟飞机 B 到达时间为 5、盘旋 0 分钟、降落耗时 1 分钟。如果按到达时间先安排 AA 从 0 到 10 占着跑道B 只能在 10 开始但 B 最晚开始时间是 5所以线性判断会误判为不可能。其实 B 先降落后 A 再降落才可行。这就说明这道题必须搜索所有排列顺序任何“先排序再贪心”的思路都可能出错。2.3 long long 与输入解析阴沟里翻船这类数据结构的题输入量通常不大但数值范围可能很大。我之前就因为 int 溢出吃过亏t1e9, d1e9td2e9int 最大值是 2147483647按说没有溢出但如果 t 和 d 都取 1e9 稍微多一点就会超。更稳妥的做法是全程使用 long long并且读入时直接读到 long long 变量里。还有一个小细节如果你混用 cin 和 scanf又关闭了同步流可能会导致读入顺序错乱。n 比较小的时候老老实实用 cin 就行或者统一用 scanf/printf。我见过有人在循环里先 scanf 读 n再用 cin 读三个数关掉 ios::sync_with_stdio(false) 之后第二组数据直接读不出来提交时只过前两个样例就超时或读入失败。2.4 只跑一遍样例就提交遗漏隐藏边界很多人拿到题样例能过就立刻提交然后盯着“两项案例通过”发呆。要知道样例通常只给最普通的场景隐藏测试点会覆盖这些要命的情况飞机数量为 1而且 d 为 0。所有飞机的降落窗口完全错开可以无缝衔接。有一架飞机窗口非常短必须在最后安排。某一架飞机到达时间特别晚导致前面所有飞机都要等它。这些边界其实都可以在本地提前构造验证。别急着提交先花五分钟把自己能想到的极端情况写成测试用例跑一遍再交。这一个习惯能让你的通过率立刻提升一大截。3. 一个能稳定 AC 的写法回溯框架与可选优化3.1 标准回溯版数据量小的时候直接过这类题通常数据范围给得很保守n 不超过 1010! 的排列也就 3628800 种回溯加上剪枝完全够用。下面是我推荐的标准写法直接抄就能用#include bits/stdc.h using namespace std; typedef long long ll; int n; ll t[15], d[15], l[15]; bool vis[15]; bool dfs(int pos, ll runwayFree) { if (pos n) return true; // 所有飞机都已安排完 for (int i 0; i n; i) { if (vis[i]) continue; ll start max(runwayFree, t[i]); // 跑道空闲时间和飞机到达时间取较晚 if (start t[i] d[i]) continue; // 错过了最晚开始时间直接剪掉 vis[i] true; if (dfs(pos 1, start l[i])) return true; vis[i] false; // 回溯撤销选择 } return false; } int main() { int T; cin T; while (T--) { cin n; for (int i 0; i n; i) { cin t[i] d[i] l[i]; } memset(vis, 0, sizeof vis); if (dfs(0, 0)) cout YES\n; else cout NO\n; } return 0; }这个代码的核心就两行一行算 start一行判断 start 是否在窗口内。看到max(runwayFree, t[i])千万不要简化成runwayFree因为飞机晚到时跑道早早就空出来了但飞机还没到实际开始时间必须等飞机到达。同样不能简化成t[i]因为跑道可能还忙着必须等上一架完成。3.2 三个减少无效分支的实用技巧如果你的数据范围稍微大一点n 到 15 左右纯回溯可能有点吃力可以尝试下面三个技巧。先说最简单的跳过完全重复的飞机。如果两架飞机的 t、d、l 完全相同在当前状态下先尝试哪一架效果一样。如果第一架尝试失败第二架也没必要再试。实现方式可以先把飞机按参数排序然后在循环里加一个判断如果当前飞机和上一架参数完全相同并且上一架还没被访问说明上一架已经尝试过且失败直接 continue。第二个技巧是状态压缩 DP。n 不超过 20 时可以用dp[mask]表示已经安排完 mask 集合内所有飞机后跑道最快的空闲时间。由于跑道空闲时间越早越有利于后续安排所以每个集合只保留最小的完成时间即可。转移时枚举下一个要安排的飞机 i判断它能否在窗口内开始降落然后更新新状态ll dp[1 20]; dp[0] 0; for (int mask 0; mask (1 n); mask) { if (dp[mask] INF) continue; for (int i 0; i n; i) { if (mask (1 i)) continue; ll start max(dp[mask], t[i]); if (start t[i] d[i]) continue; dp[mask | (1 i)] min(dp[mask | (1 i)], start l[i]); } }这个 DP 比回溯稳得多因为它天然避免了重复状态的搜索而且转移条件极其清晰。如果你只是在做练习建议两种写法都写一遍对理解“状态压缩”和“回溯剪枝”的区别非常有帮助。第三个技巧是搜索顺序优化。在回溯的每一层优先尝试当前 start 最小的飞机可以更快地找到可行解或者在找不到解时更快地触发剪枝。但这只是一个启发式优化不保证一定比固定顺序快也不建议在没搞懂回溯原理之前去依赖它。对于 n≤10完全没必要。3.3 构造自己的边界测试轮我最推荐的做法是在提交之前先构造一组边界用例确保代码能正确响应。下面这些用例基本覆盖了常见的隐藏测试点测试用例预期结果说明n1, t0, d0, l10YES单架飞机且不允许盘旋n1, t5, d3, l10YES开始时间为5完成15完全合法n2, 飞机A: 0 0 10, 飞机B: 5 10 1YES必须安排A先降落B可以等n2, 飞机A: 0 0 10, 飞机B: 5 0 1NOB窗口很短但A占着跑道反之A等不了n3, 三架飞机窗口依次错开0 0 1, 1 0 1, 2 0 1YES标准流水线n3, 三架飞机都在同一时间到达视降落时间而定检查所有排列构造用例时我习惯用一个简单的原则每架飞机都设计一个“窗口结束前最后一刻才开始降落”的场景看看代码会不会误判。比如 t0, d5, l6 这种用例如果代码用完成时间做判断一定出错。把这些用例在本地跑一遍再提交基本就能避开“样例过了但隐藏用例挂掉”的尴尬。4. 现场排查实录与调试心得4.1 用打印回溯现场找坏点调这类题最有效的方法是在 dfs 函数里加打印观察每次尝试的状态。我已经养成习惯在进入循环前打印当前 pos 和 runwayFree在每次选中一架飞机后打印“尝试第 i 架startxxxfinishxxx”。日志长这样进入 dfs, pos0, runwayFree0 尝试第0架, t0, d5, l6, start0, finish6 进入 dfs, pos1, runwayFree6 尝试第1架, t5, d0, l1, start6, finish7如果发现某一步 start 明显小于 t[i]说明 max 写漏了如果某一步明明 start t[i]d[i] 但代码还是继续递归说明判断条件写错了。打印日志之后错误点几乎一眼就能看出来。调试完记得把打印注释掉否则大量输出会导致超时。4.2 我的两个阴间 Bug 复盘我第一次做这道题只过了两个案例查了一晚上才发现两个问题。第一个是把转移公式写成了start max(runwayFree, t[i]) l[i]然后在递归里传入了 start这就把“开始时间”和“完成时间”混在了一起。逻辑上下一架飞机的跑道空闲时间应该是上一架的完成时间而我把它写成了当前飞机的开始时间。结果所有后续窗口都被提前样例又恰好没有触发这种错误提交就只过了一项。这个教训告诉我变量的命名必须和实际含义一一对应不能为了省变量名就随便复用。第二个更蠢判断条件写成了if (runwayFree t[i] d[i]) continue;漏掉了 max。当跑道空闲时间远早于飞机到达时间时runwayFree 看起来没有超过最晚开始时间但飞机其实已经错过了自己的窗口。比如跑道 0 时刻就空了飞机 100 时刻才到d0跑道空闲时间确实不大于 100但这架飞机在 100 时刻才到达而最晚开始时间也是 100虽然能赶上但如果 d0 会错。这个坑的教训是判断窗口时必须比较“实际开始时间”和“最晚开始时间”而实际开始时间是跑道空闲时间和到达时间的较大者。4.3 交之前先做的三件事根据我的经验提交前做下面三件事能大幅提高通过率第一写一个全排列暴力版本和数据量不大时的回溯版本对拍。暴力版本直接枚举所有排列顺序检查是否可行。随机生成几百组数据只要两个版本结果不一致就说明回溯代码有隐蔽逻辑错误。对拍是排查回溯问题最可靠的方法没有之一。第二检查所有用于时间计算的变量类型。把所有 t、d、l、start、finish 全部定义为 long long绝对不要用 int。就算题目说数据范围小也建议用 long long因为代码以后复用起来更安全。第三确认多组样例之间的状态清理。重点看 vis 数组是否每轮都重置全局变量 n 是否被覆盖以及读入操作是否在每组样例开始前正确执行。这三类错误在所有回溯题里都是高频事故飞机降落问题也不例外。最后分享一点个人经验我后来重新审视这道题发现它考的不是“会不会写递归”而是“能不能把一个动态过程里的每个时间点都搞清楚”。机场调度模型其实非常贴近现实你既要尊重飞机到达时间又要考虑跑道占用还要理解每架飞机愿意等待的极限。把这三个要素拆开按照“实际开始时间 max(跑道空闲, 飞机到达)”这个公式一步步推代码自然就对了。如果你现在还卡在“只能通过两项案例”先把判断条件和转移公式抄在纸上逐行模拟一遍再打开代码对比。大部分问题都出在那一两个max和 l[i]上。改完之后记得把边界测试轮跑一遍再提交。这道题值得你多花一点时间因为回溯状态恢复和窗口判断的技巧在别的调度类题目里还会反复出现。
