[蓝桥杯] 飞机降落(C语言)
洛谷P9241 [蓝桥杯 2023 省 B] 飞机降落,c语言版本
文章共1,400字 · 阅读需要大约5分钟
一键AI生成摘要,助你高效阅读
问答
·
题目链接
题目理解
给定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;
}
————(如有问题,欢迎评论区提问)————
更多推荐
已为社区贡献2条内容
所有评论(0)