蓝桥杯算法题之飞机降落_蓝桥杯 飞机降落

题目描述：

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时刻完成降落。
对于第二组数据，无论如何安排，都会有飞机不能及时降落。
评测用例规模与约定
N≤2。对于30％的数据，N≤2。
对于100％的数据，1≤T≤10,1≤N≤10;0≤Ti,Di,Li≤10^5。

完整代码：

#include <iostream>
 
using namespace std;
 
const int MAX_N = 11;
int N, T[MAX_N], D[MAX_N], L[MAX_N];
bool used[MAX_N], have_answer;
 
void dfs(int x, int tim) {
    
    if (x == N) {
        have_answer = true;
        return;
    }
    if (have_answer) return;
 
    for (int i = 1; i <= N; i++) {
        if (!used[i] && tim <= T[i] + D[i]) {
            used[i] = true;//如果符合降落条件，飞机开始降落
            int finish_time = max(tim, T[i]) + L[i];//当前时刻和飞机最早降落时刻的最大值再加上降落时间可以得到飞机的降落完成时间
             dfs(x + 1, finish_time);
            if (have_answer) return;
            used[i] = false;
        }
    }
}
 
void solve() {
    cin >> N;
    have_answer = false;//数据提前清空
    
    for (int i = 1; i <= N; i++) {
        cin >> T[i] >> D[i] >> L[i];
        used[i]=false;//恢复现场
    }
    dfs(0, 0);
    if (have_answer) cout <<"YES\n";
    else cout <<"NO\n";
}
 
int main() {
    int T;
    cin >> T;
    while (T--) {
        solve();
    }
    return 0;
}

注：该题的样例输出是YES和NO但是提交的时候通过的是YES和YES，如有不太对的地方请大家指正。