蓝桥杯2023年第十四届省赛真题-飞机降落

蓝桥杯2023年第十四届省赛真题-飞机降落 - C语言网 (dotcpp.com)

“蓝桥杯前一周才开始写真题，练算法，能赢嘛？会赢的（bushi五条）”

题目描述

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

实现思路

一开始我试图用贪心和排序安排每个飞机的起降时间，但是只通过了百分之60。看来不能达到最优。于是又想起了DFS可以考虑全部的情况。那么就用DFS去遍历所有可能的情况，只要找到以一种可以全部迫降的方案就可以输出YES！

实现代码

#include <iostream>
#include <vector>

using namespace std;
typedef long long ll;
class plane
{
public:
    ll s;
    ll e;
    ll c;
};
const ll N = 1e3;
vector<plane> a(N);
vector<bool> b(N);
ll n;
ll size;
bool can;

void dfs(ll deepth, ll usetime)
{
    // deepth深度 第几个迫降的飞机
    // usetime当前的时间
    if (can)
        return;
    if (deepth == size)
    {
        can = true;
        return;
    }
    for (int i = 1; i <= size; i++)
    {
        if (b[i] == false && usetime <= (a[i].s + a[i].e))
        {
            // 如果当前的时间不能起飞 那么就不起飞
            b[i] = true;
            // usetime = max(usetime, a[i].s) + a[i].c;
            // 每个分支都有不同的usetime
            // 所以不能用一个usetime
            dfs(deepth + 1, max(usetime, a[i].s) + a[i].c);
            if (can)
            {
                return;
            }
            b[i] = false;
        }
    }
}

void solve()
{
    cin >> size;
    can = false;
    for (ll i = 1; i <= size; i++)
    {
        b[i] = false;
        // 每次不同的飞机要记得把状态数组重置
        cin >> a[i].s >> a[i].e >> a[i].c;
    }
    dfs(0, 0);
    if (can)
    {
        cout << "YES" << endl;
    }
    else
    {
        cout << "NO" << endl;
    }
}

int main()
{
    cin >> n;
    while (n--)
    {
        solve();
    }
    return 0;
}

实现细节注意 

1. b状态判断数组在每轮飞机迫降前需要false初始化，别忘了。
2. 每个DFS分支的usetime是不一样，不能设置一个全局变量一概而论。只需要告诉dfs当前时间即可。