[蓝桥杯]飞机降落（C语言）

阅读本书更多章节>>>>

        题目链接

        [蓝桥杯 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;}

————（如有问题，欢迎评论区提问）————

阅读本书更多章节>>>>

本文链接：https://www.kjpai.cn/gushi/2024-04-06/154941.html，文章来源：网络cs，作者：言安琪，版权归作者所有，如需转载请注明来源和作者，否则将追究法律责任！