飞机降落问题：回溯算法、窗口判断与边界调试全解析

如果你也正被这个“飞机降落问题”卡住，提交结果只显示两项案例通过，先别急着怀疑人生。这道题我当年也栽过：本地样例怎么跑怎么对，逻辑读一遍没毛病，可提交后就是过不了几个测试点。后来花了一晚上逐层打日志，才发现问题根本不在“会不会回溯”，而在几处特别容易忽略的时间边界。这篇文章把这道题的完整解法和排查思路写下来，希望能帮同样卡住的人少走点弯路。

1. 别急着改代码，先确认你理解的是哪个“飞机降落问题”

1.1 题面在说什么：一个机场调度模型

飞机降落问题的题面通常长这样：有 n 架飞机，第 i 架有一个到达时间 t，一个可盘旋时间 d，一个降落占用跑道时间 l。飞机可以在到达后的任意时刻开始降落，但不能晚于 t+d，而且开始降落的时间不能早于 t。跑道同一时间只能服务一架飞机。问是否存在一个降落顺序，让所有飞机都能成功落地。

很多人把“可盘旋时间”理解成“可以一直等到 d 分钟、然后在任意时刻降落完成”，这是第一个误区。盘旋时间的真正含义是：飞机最多只能在空中多等 d 分钟，所以它最晚的开始降落时间是 t+d，而不是说降落过程必须在 t+d 前结束。

放在只有一个工位的汽车维修铺里理解会更直观：每辆车有一个最早到店时间 t，顾客最多愿意等到 t+d，维修要占工位 l 分钟。老板能不能把这批顾客全服务完？问题抽象后，唯一要决策的就是每个顾客（飞机）的进店顺序。飞机晚到没关系，只要在顾客离开前开始维修就行。

1.2 代码里最容易错的三个“窗口边界”

先说第一架飞机的处理。很多人的回溯函数里，代表“跑道空闲时间”的变量 last 初始化为 0，这本身没错，但第一架飞机如果到达时间很晚，比如 t=100，跑道从 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，不是完成时间。我给你一个反例：t=0, d=5, l=6。如果写成了last + l[i] > t[i] + d[i]来判断，last=0 时 0+6=6 > 5，会判成不合法，但实际上飞机在 0 时刻开始降落，6 时刻完成，完全在允许范围内。这个错法非常隐蔽，因为样例里很少给这种“窗口很短但降落很长”的数据。

第三个坑是数据溢出。t 和 d 的范围如果达到 1e9 量级，t+d 用 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 对“最晚开始时间”的错误理解

我见过三种典型的错误理解，每种都能让你的代码只过部分用例。

第一种是把 t+d 当成“降落完成的最晚时间”。假设 t=0, d=5, l=6，飞机在 0 时刻开始降落，6 时刻完成。如果代码用last + l[i] > t[i] + d[i]做判断，0+6 > 5，直接判不合法。但事实上这架飞机完全来得及。所以判断条件必须针对开始时间，而不是完成时间。

第二种是忽略了飞机到达时间的约束。有些简化写法只判断last > t[i] + d[i]，然后认为只要跑道足够早空闲就能安排。可如果 t[i] 本身很大，比如 last=0, t=100, d=0，跑道确实空闲，但飞机要等到 100 才能开始降落，而它最晚开始时间也是 100，表面上看 last=0 没有超过 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 分钟。如果按到达时间先安排 A，A 从 0 到 10 占着跑道，B 只能在 10 开始，但 B 最晚开始时间是 5，所以线性判断会误判为不可能。其实 B 先降落后 A 再降落才可行。这就说明，这道题必须搜索所有排列顺序，任何“先排序再贪心”的思路都可能出错。

2.3 long long 与输入解析：阴沟里翻船

这类数据结构的题，输入量通常不大，但数值范围可能很大。我之前就因为 int 溢出吃过亏：t=1e9, d=1e9，t+d=2e9，int 最大值是 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 不超过 10，10! 的排列也就 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 构造自己的边界测试轮

我最推荐的做法是，在提交之前先构造一组边界用例，确保代码能正确响应。下面这些用例基本覆盖了常见的隐藏测试点：

构造用例时，我习惯用一个简单的原则：每架飞机都设计一个“窗口结束前最后一刻才开始降落”的场景，看看代码会不会误判。比如 t=0, d=5, l=6 这种用例，如果代码用完成时间做判断，一定出错。把这些用例在本地跑一遍，再提交，基本就能避开“样例过了但隐藏用例挂掉”的尴尬。

4. 现场排查实录与调试心得

4.1 用打印回溯现场找坏点

调这类题，最有效的方法是在 dfs 函数里加打印，观察每次尝试的状态。我已经养成习惯：在进入循环前打印当前 pos 和 runwayFree，在每次选中一架飞机后打印“尝试第 i 架，start=xxx，finish=xxx”。日志长这样：

进入 dfs, pos=0, runwayFree=0 尝试第0架, t=0, d=5, l=6, start=0, finish=6 进入 dfs, pos=1, runwayFree=6 尝试第1架, t=5, d=0, l=1, start=6, finish=7

如果发现某一步 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 时刻才到，d=0，跑道空闲时间确实不大于 100，但这架飞机在 100 时刻才到达，而最晚开始时间也是 100，虽然能赶上，但如果 d<0 会错。这个坑的教训是：判断窗口时，必须比较“实际开始时间”和“最晚开始时间”，而实际开始时间是跑道空闲时间和到达时间的较大者。

4.3 交之前先做的三件事

根据我的经验，提交前做下面三件事，能大幅提高通过率：

第一，写一个全排列暴力版本，和数据量不大时的回溯版本对拍。暴力版本直接枚举所有排列顺序，检查是否可行。随机生成几百组数据，只要两个版本结果不一致，就说明回溯代码有隐蔽逻辑错误。对拍是排查回溯问题最可靠的方法，没有之一。

第二，检查所有用于时间计算的变量类型。把所有 t、d、l、start、finish 全部定义为 long long，绝对不要用 int。就算题目说数据范围小，也建议用 long long，因为代码以后复用起来更安全。

第三，确认多组样例之间的状态清理。重点看 vis 数组是否每轮都重置，全局变量 n 是否被覆盖，以及读入操作是否在每组样例开始前正确执行。这三类错误在所有回溯题里都是高频事故，飞机降落问题也不例外。

最后分享一点个人经验

我后来重新审视这道题，发现它考的不是“会不会写递归”，而是“能不能把一个动态过程里的每个时间点都搞清楚”。机场调度模型其实非常贴近现实：你既要尊重飞机到达时间，又要考虑跑道占用，还要理解每架飞机愿意等待的极限。把这三个要素拆开，按照“实际开始时间 = max(跑道空闲, 飞机到达)”这个公式一步步推，代码自然就对了。

如果你现在还卡在“只能通过两项案例”，先把判断条件和转移公式抄在纸上逐行模拟一遍，再打开代码对比。大部分问题都出在那一两个max和+ l[i]上。改完之后，记得把边界测试轮跑一遍，再提交。这道题值得你多花一点时间，因为回溯状态恢复和窗口判断的技巧，在别的调度类题目里还会反复出现。