洛谷P9241 [蓝桥杯 2023 省 B] 飞机降落
题目描述
N 架飞机准备降落到某个只有一条跑道的机场。其中第 i 架飞机在 Ti 时刻到达机场上空，到达时它的剩余油料还可以继续盘旋 Di 个单位时间，即它最早可以于 Ti 时刻开始降落，最晩可以于 Ti+Di 时刻开始降落。降落过程需要 Li 个单位时间。
一架飞机降落完毕时，另一架飞机可以立即在同一时刻开始降落，但是不能在前一架飞机完成降落前开始降落。
请你判断 N 架飞机是否可以全部安全降落。
输入格式
输入包含多组数据。
第一行包含一个整数 T，代表测试数据的组数。
对于每组数据，第一行包含一个整数 N。
以下 N 行，每行包含三个整数 Ti,Di,Li。
输出格式
对于每组数据，输出 YES 或者 NO，代表是否可以全部安全降落。
输入输出样例
输入
2 3 0 100 10 10 10 10 0 2 20 3 0 10 20 10 10 20 20 10 20输出
YES NO
说明/提示
【样例说明】
对于第一组数据，可以安排第 3 架飞机于 0 时刻开始降落，20 时刻完成降落。安排第 2 架飞机于 20 时刻开始降落，30 时刻完成降落。安排第 1 架飞机于 30 时刻开始降落，40 时刻完成降落。
对于第二组数据，无论如何安排，都会有飞机不能及时降落。
【评测用例规模与约定】
对于 30% 的数据，N≤2。
对于 100% 的数据，1≤T≤10，1≤N≤10，0≤Ti,Di,Li≤105。
蓝桥杯 2023 省赛 B 组 D 题。
P9241 [蓝桥杯 2023 省 B] 飞机降落 - 洛谷
题目及思路：这题先看数据范围，飞机个数是1≤N≤10，所以我们可以通过DFS枚举所有可能的降落顺序，验证是否存在满足条件的排列。若存在任意一种可行顺序，则返回"YES"，否则返回"NO"。
代码呢主要就是套用dfs模板，然后还有其他一些地方解释一下。
代码解释：
-
数据结构：
-
plane结构体存储飞机的到达时间t、最大盘旋时间d（即在t + d之前必须开始降落）和降落所需时间l。
-
-
DFS函数：
-
参数：
cnt表示已降落飞机数，last表示上一架飞机完成降落的时间，planes为飞机数组。 -
终止条件：当所有飞机都已降落（
cnt >= n），设置成功标志flag = 1。 -
递归逻辑：遍历所有未使用的飞机，若当前飞机的时间窗口允许在
last之后开始降落（planes[i].t + d >= last），则标记为已使用，并计算下一架飞机的最早可用时间（nextTime = max(last, t) + l），继续递归。
-
这里解释一下nextTime为什么要取两者的较大值。飞机只能在到达之后才能开始降落，所以如果上一架飞机降落完成的时间`last`比当前飞机的到达时间`t`晚，那么当前飞机必须等到`last`才能开始降落。反之，如果当前飞机到达时间`t`更晚，那么它需要等到`t`才能开始。因此，`nextTime`实际上是当前飞机降落结束的时间，也就是下一架飞机可以开始降落的最早时间。
以下是我提交通过的C语言代码，仅供参考：
#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<string.h>
#include<ctype.h>
#include<limits.h>
#include<stdlib.h>
#include<math.h>
#include <stdbool.h>
int t, n = 0; bool used[1000]; int flag = 0;
typedef struct
{
int t;
int d;
int l;
}plane;
void dfs(int cnt, int last, plane *planes)
{
//last：表示上一架飞机完成降落的结束时间（即跑道可用的起始时间）。
if (cnt >= n)
{
flag = 1;
return;
}
for (int i = 0; i < n; i++)
{
if (!used[i])
{
if (planes[i].t + planes[i].d >= last)
{
used[i] = true;
// nextTime：当前飞机完成降落后，跑道再次可用的时间（即下一架飞机的最早可用时间）。
int nextTime = (last > planes[i].t ? last : planes[i].t) + planes[i].l;
dfs(cnt + 1, nextTime, planes);
used[i] = false;
}
}
}
}
int main()
{
scanf("%d", &t);
while (t--)
{
memset(used, 0, sizeof(used));
plane planes[11];
scanf("%d", &n);
for (int i = 0; i < n; i++)
{
scanf("%d %d %d", &planes[i].t, &planes[i].d, &planes[i].l);
}
flag = 0;
dfs(0, 0, planes);
if (flag == 1)
{
printf("YES\n");
}
else
{
printf("NO\n");
}
}
return 0;
}