蓝桥杯飞机降落dfs深度解析

蓝桥杯14届省赛[飞机降落]

题目描述

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。

##　解题思路

1.看数据范围： 共有 T 组数据，T 最大为 10， N最大为 10， 所以可以先想暴力解法。

2.暴力解法做法： 对于 N 架飞机， 枚举出他们的全排列，然后看其中一种能否安全的降落所有飞机。

我觉得这个题的难点主要有两点：

• 我看到这个题的第一时间会想到排序，因为我没有看到数据范围，所以想到的是贪心排序后，能否按照排序后的结果去安全的降落飞机。也就是说，第一时间可能想不到暴力搜索。（可能是题刷少了）
• 在暴力搜索的过程中，判断飞机是否能够安全停靠的条件很难想出来。

code

1.写出深度优先搜索模板 (顺便回顾如何全排列)

void dfs(int step) {
    if(step == n ) {
        结束条件
        return ;
    }
    
    for(int i = 0; i < n; i ++) {
        if(!book[i]) {
            book[i] = true;
            dfs(step + 1);
            book[i] = false;
        }
    }
}

2.复习全排列写法

#include <iostream>
using namespace std;

const int N = 20;
int n, book[N], a[N];

void dfs(int step) {
    if(step == n) {
        for(int i = 0; i < n; i ++) cout<<a[i]<<" ";
        cout<<endl;
        return ;
    }
    
    for(int i = 0; i < n; i ++) {
        if(!book[i]) {
            book[i] = 1;
            a[step] = i + 1;
            dfs(step + 1);
            a[step] = 0;
            book[i] = 0;
        }
     }
}

int main() {
    
    cin>>n;
    dfs(0);
    
    return 0;
}

3.写出本题飞机能安全停靠的条件判断

由于飞机到达时间 T , 可以盘旋时间 D，降落需要时间 L

可以知道飞机只要在 T ~ T + D 这段时间降落就可以停下，当然安全降落会消耗时间 L

那么也就是说，停靠上一架飞机时间 time 满足 T <= time <= T + D, 飞机就可以安全降落， 然后降落会耗费时间 L， 也就是停靠下一次飞机的时候。当前时间 time更新为 time = time + L

你以为这样就万事大吉了吗？错！！！

我们还没有考虑到， 其实当 time < T 的时候，也就是说，上一架飞机安全停靠后，过了一段时间当前这架飞机才到机场，也就是说，当

time < T 的时候，实际上我们当前飞机都不用耗费燃料 D 盘旋，也就是说，time < T 不影响我们能否安全降落，也就是说可以去除条件 T

< time, 也就是说， 当 time <= T + D 的时候就可以安全降落。

你以为这样又往事大吉了吗？错！！！

当时间更新的时候，我们需要考虑到，当飞机停靠时间 time 在时间 T之前，我们真实去停靠完成这架飞机的时间应该是 T +Ｌ而不是 time + L,所以更新时间可以写为 time = max(time, T) + L;

完整代码：

#include <iostream>
using namespace std;

const int N = 20;
int n, t, book[N], T[N], D[N], L[N];
bool result;

void dfs(int step, int time) {
		if(step == n)  {
            result = true;
    		return;
		}    
		
	        for(int i = 0; i < n; i ++) {
	            
            if(!book[i] && time <= T[i] + D[i]) {
                 book[i] = 1;
           		 dfs(step + 1, max(time, T[i]) + L[i]);
           		 book[i] = 0;
            }
                
        }
        return;
}

int main() {
    
    cin>>t;
    while(t --) {
    	cin>>n;
        for(int i = 0; i < n; i ++) cin>>T[i]>>D[i]>>L[i];
        
		result = false;
        dfs(0, 0);
        
        if(result) cout<<"YES"<<endl;
        else cout<<"NO"<<endl;
    }
    
    return 0;
}