题目描述

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

个人分析

这道题目我使用的是一个深度优先搜索的方法 

这是题解的dfs函数 对dfs函数进行分析就可以知道为什么这样写了

void dfs(int x, int time)
{
   if(have_answer == true)
   {
      return;
   }
   if(x == N)
   {
      have_answer = true;
      return;
   }
   for(int i = 1; i <= N; i++)
   {
      if(used[i] == false && time <= T[i] + D[i])
      {
          used[i] = true;
          dfs(x+1,max(time, T[i]) + L[i]);
          if(have_answer == true)
          {
             return;
          }
          used[i] = false;
      }
   }
}

dfs函数参数是x和time x代表的是当前正在降落第几架飞机 time代表的是当前的时刻

我们只要有一个答案便可以输出YES，所以我们只需要定义一个have_answer

在判断飞机是否可以降落的时候 我们需要使用used来记录已经降落的飞机 然后进行for循环来遍历 所有的飞机 如果遇到飞机没有降落并且当前的时刻是小于飞机的最晚起飞时间的 就可以考虑降落这个飞机

max(time, T[i]) + L[i]是说明我们的最早降落的时间得等到飞机到达才可以

题解代码

#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];
bool have_answer;
 
void dfs(int x, int time)
{
   if(have_answer == true)
   {
      return;
   }
   if(x == N)
   {
      have_answer = true;
      return;
   }
   for(int i = 1; i <= N; i++)
   {
      if(used[i] == false && time <= T[i] + D[i])
      {
          used[i] = true;
          dfs(x+1,max(time, T[i]) + L[i]);
          if(have_answer == true)
          {
             return;
          }
          used[i] = false;
      }
   }
}
 
void solve()
{
  have_answer = false;
  cin >> N;
  for(int i = 1; i <= N; i++)
  {
     used[i] = false;
     cin >> T[i] >> D[i] >> L[i];
  }
  dfs(0, 0);
  if(have_answer == false)
  {
      cout << "NO" << endl;
  }
  else
  {
     cout << "YES" << endl;
  }
}
 
int main()
{
  int n;
  cin >> n;
  for(int i = 0; i < n; i++)
  {
     solve();
  }
 return 0;
}