挺有意思的一道题,分享给大家

题目链接

P9241 [蓝桥杯 2023 省 B] 飞机降落 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

题目描述

【洛谷】P9241 [蓝桥杯 2023 省 B] 飞机降落-LMLPHP

输入格式

【洛谷】P9241 [蓝桥杯 2023 省 B] 飞机降落-LMLPHP

输出格式

【洛谷】P9241 [蓝桥杯 2023 省 B] 飞机降落-LMLPHP

输入输出样例

【洛谷】P9241 [蓝桥杯 2023 省 B] 飞机降落-LMLPHP

说明/提示

【洛谷】P9241 [蓝桥杯 2023 省 B] 飞机降落-LMLPHP


思路

一开始尝试贪心能不能做,但是不好确定飞机的顺序

因为这题的数据量较小,对时间复杂度没有要求,可以直接用深搜全排列一下找正解

代码

#include <bits/stdc++.h>
using namespace std;

struct info // 用于存储每架飞机的三个时间
{
    info(int a, int b, int c)
        : _T(a), _D(b), _L(c)
    {}

    int _T; // 到达时间
    int _D; // 最大盘旋时间
    int _L; // 降落花费的时间
};

static vector<bool> visit; // 用于检测飞机是否已经降落
static vector<info> plane; // 存储飞机的各项时间
static int n;              // 飞机个数

bool dfs(int i, int time) // dfs返回bool类型的值,如果某条路径走得通则返回true,走不通则false
{
    if (i == n) // 当i==n,说明飞机全部降落
        return true;
    for (int k = 0; k < n; k++) // 通过遍历进行飞机的全排列,逐个排除无法成功降落的飞机顺序
    {
        if (!visit[k] && plane[k]._T + plane[k]._D >= time) // 降落条件:没有降落过 且 飞机到达的时间+可以继续盘旋的时间>=前面所有飞机降落花费的时间
        {
            visit[k] = true; // 标记飞机已经降落
            if (dfs(i + 1, max(time, plane[k]._T) + plane[k]._L)) // i+1记录降落的飞机数量,而不是k+1,如果飞机到达的时间在time之后,则以到达时间为标准+降落花费的时间
                return true;
            visit[k] = false; // 到这里,说明先降落第k架飞机的策略行不通,回溯到飞机未降落的状态
        }
    }
    return false; // 循环结束,说明该层递归中无论选择哪架飞机降落都无法成功,则返回false
}

int main()
{
    int t;
    cin >> t;
    while (t--) // 当t为0说明全部测试组完毕
    {
        cin >> n;
        visit = vector<bool>(n, false);
        for (int i = 0; i < n; i++) // 存入n架飞机的各项时间
        {
            int a, b, c;
            cin >> a >> b >> c;
            plane.push_back(info(a, b, c));
        }
        if (dfs(0, 0)) // 如果存在可以成功降落的飞机顺序,则打印YES
            cout << "YES" << endl;
        else
            cout << "NO" << endl;
        plane.clear(); // 清除plane中的数据,为下一组做准备
    }
    return 0;
}

【洛谷】P9241 [蓝桥杯 2023 省 B] 飞机降落-LMLPHP

完.

03-31 06:52