题目链接
[蓝桥杯 2023 省 B] 飞机降落 - 洛谷
题目理解
给定n个飞机的降落时间段，每个飞机有一个最早降落时间和最晚降落时间。飞机需要在指定的时间段内降落，并且每个飞机的降落时间是固定的。现在需要判断是否存在一种降落顺序，使得所有飞机都能在规定的时间段内降落。
解题思路
这是一个典型的回溯算法问题。我们可以使用深度优先搜索（DFS）来解决。
具体步骤如下：
定义一个结构体Node，用于存储飞机的最早降落时间、最晚降落时间和降落需要的时间。定义全局变量t表示测试用例的数量，n表示飞机的数量，vis数组用于标记飞机是否已经降落，flag表示是否存在一种降落顺序。实现dfs函数，该函数用于进行深度优先搜索。参数deep表示当前搜索的深度，now表示当前时间。在dfs函数中，首先判断是否已经搜索到了所有飞机（即deep == n），如果是，则将flag置为true，表示存在一种降落顺序，然后返回。在dfs函数中，使用循环遍历所有飞机，对于每个飞机，判断是否已经降落（即0==vis[i]）以及飞机的最晚降落时间是否早于当前时间（即fj[i].r < now）。如果满足这两个条件中任一，则该顺序不能完成所有飞机的降落，进行剪枝，直接返回。在dfs函数中，如果飞机未降落且最晚降落时间不早于当前时间，将该飞机标记为已降落（vis[i] = 1），然后根据飞机的最早降落时间和当前时间，计算下一个飞机的降落时间，并递归调用dfs函数。在递归调用dfs函数之后，需要取消对当前飞机的标记（vis[i] = 0），以便进行下一次搜索。在主函数中，读取测试用例的数量t，然后循环读取每个测试用例的飞机数量n和飞机的降落时间信息。对于每个测试用例，先将flag置为false，然后遍历每个飞机，将其标记为已降落，并调用dfs函数进行搜索。最后根据flag的值输出结果。 完整代码（详解注释版）
#include <stdio.h>#include <stdbool.h>#include <string.h> struct Node { int l; // 飞机最早能降落的时间 int r; // 飞机最晚能降落的时间 int t; // 飞机降落需要的时间}; int t, n, vis[15]; // t表示测试用例的数量，n表示飞机的数量，vis数组用于标记飞机是否已经降落bool flag; // 是否存在一种降落顺序struct Node fj[15]; // 存储飞机的降落时间信息 void dfs(int deep, int now) // 深度优先搜索函数，now表示当前时间{ if (deep == n) // 如果已经搜索到了所有飞机，将flag置为true，表示存在一种降落顺序{ flag = true; return; } for (int i = 1; i <= n; i++) {if(vis[i]==1)//如果飞机已经降落，直接跳过向下进行{continue;} if (fj[i].r < now){return; // 如果飞机的最晚降落时间早于当前时间，进行剪枝，直接返回} if (0==vis[i] && fj[i].r >= now) { vis[i] = 1; // 标记该飞机已经降落 if (fj[i].l > now){dfs(deep + 1, fj[i].l + fj[i].t); // 如果飞机的最早降落时间比当前时间晚，计算下一个飞机的降落时间为最早降落时间加上降落需要的时间} else{dfs(deep + 1, now + fj[i].t); // 否则，计算下一个飞机的降落时间为当前时间加上降落需要的时间} vis[i] = 0; // 取消对当前飞机的标记，以便进行下一次搜索 } }} int main() { scanf("%d", &t); // 读取测试用例的数量 memset(vis, 0, sizeof(vis)); // 初始化vis数组为0 while (t--) { scanf("%d", &n); // 读取飞机的数量 flag = false; // 初始化flag为false int k; for (int i = 1; i <= n; i++) { scanf("%d %d %d", &fj[i].l, &k, &fj[i].t); // 读取每个飞机的降落时间信息 fj[i].r = fj[i].l + k; // 计算飞机的最晚降落时间 } for (int i = 1; i <= n; i++) { vis[i] = 1; // 将飞机标记为已降落 dfs(1, fj[i].l + fj[i].t); // 调用dfs函数进行搜索 vis[i] = 0; // 取消对当前飞机的标记，以便进行下一次搜索 } if (flag) printf("YES\n"); // 根据flag的值输出结果 else printf("NO\n"); } return 0;}————（如有问题，欢迎评论区提问）————
